Sum of Subarray Minimums
Compute the sum of the minimum values of every contiguous subarray, using a monotonic stack.
Input format
The first line contains N. The second line contains N positive integers.
Output format
Print the sum of min(b) over every contiguous subarray b.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
4
3 1 2 4Expected output
17Example 2
Input
3
11 81 94Expected output
289