340. Efficient Subarray Sum

0

Medium

Adarsh has a given array of integers

**arr**and wants to find the sum of the smallest element from each subarray. However, this process takes a long time. Help Adarsh find the result more efficiently. The answer should be returned modulo 10^9 + 7.Input Format

The first line of input should contain an integer N, the size of the array. The second line should contain N integers representing the elements of the array.

Output Format

The output should be the sum of the smallest element of each possible subarray.

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