Subarray Minimums with Sum
Given an array A of N integers, for each element A[i], find the sum of minimums of all subarrays where A[i] is the minimum element. Calculate the total sum of these values for all i. That is, compute SUM(A[i] * count(i) * left_dist(i) * right_dist(i)) for all i, where count(i) is the number of subarrays for which A[i] is the minimum element, left_dist(i) is the number of elements to the left of A[i] (inclusive) that can be the start of such a subarray, and right_dist(i) is the number of elements to the right of A[i] (inclusive) that can be the end of such a subarray. Return the total sum modulo 10^9 + 7.
Input
The first line contains an integer N. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer, the total sum modulo 10^9 + 7.
Constraints
1 <= N <= 200000 1 <= A_i <= 10^9
Example 1
3 1 2 3
10
Subarrays: [1](min 1), [2](min 2), [3](min 3), [1,2](min 1), [2,3](min 2), [1,2,3](min 1). Contributions: 1*3 (for 1 being min in [1],[1,2],[1,2,3]) + 2*2 (for 2 being min in [2],[2,3]) + 3*1 (for 3 being min in [3]) = 3+4+3 = 10.
Example 2
4 3 1 2 4
17
Contributions: 3 (in [3]) + 1*6 (in [1], [1,2], [1,2,4], [3,1], [3,1,2], [3,1,2,4]) + 2*2 (in [2], [1,2]) + 4 (in [4]) = 3 + 6 + 4 + 4 = 17.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 1 2 3
4 3 1 2 4