Given an array of n integers (which may be negative), consider every one of its n*(n+1)/2 contiguous subarrays (including single-element subarrays and the whole array). For each subarray, take its minimum element. Sum these minimums over all subarrays, and print the sum modulo 1000000007.
Input format
Line 1: an integer n.
Line 2: n space-separated integers.
Output format
A single integer: the sum of the minimum of every contiguous subarray, modulo 1000000007 (always printed as a value between 0 and 1000000006 inclusive).
Constraints
- 1 ≤ n ≤ 100000
- -1000000 ≤ each value ≤ 1000000