460. Sum of Subarray Minimums

0

Medium

Given an array of integers, Varun has been tasked by his friend to find the sum of the minimum values (b) in every subarray of the given array. Since the sum may be large, the answer should be returned modulo 10

^{9}+ 7.Input Format

The first line of input should contain the length of the array, n.
The second line should contain n space-separated integers representing the array elements.

Output Format

The output should be the sum of the minimum values.

Example

Input

4
3 1 2 4

Output

17

Constraints

1 <= arr.length <= 3 * 10^4

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

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

Loading...

View Submissions

Console