733. Help Adarsh

0

Medium

Adarsh is free at this time. He has a given array of integers

Since the answer may be large, return the answer modulo 10^9 + 7.

**arr**, Now he is making all possible subarrays of this array and trying to find the sum of smallest element from each subarray.This process will take a long time so help him to find his result in less time.Since the answer may be large, return the answer modulo 10^9 + 7.

Input Format

First line takes integer N(size of array) as input.

Second line contains N integers to the array.

Second line contains N integers to the array.

Output Format

Print the sum of the smallest element of each possible sub array.

Example

Input

4
3 1 2 4

Output

17

Constraints

1<=N<=10^5

1<=arr[i]<=10^4

1<=arr[i]<=10^4

Loading...

View Submissions

Console