Question
Min Sum
In an enchanted realm, Ram is entrusted with an array A of N distinct integers. His task is to calculate the sum of the smallest element in every possible subarray (contiguous segment) of A.
Help Ram uncover this total to reveal the array’s hidden essence.
Input
The first line of input contains a single integer N, denoting the size of the array.
The second line of input contains N space-separated integers.
The second line of input contains N space-separated integers.
Output
The output should contain single integers, the sum of minimum element of all the subarrays in that array.
Example
Sample Input
3
1 2 3
Sample Output
10
Explanation
all subarrays [1] [1,2] [1,2,3] [2] [2,3] [3]
Sum of minimums : 1 + 1 + 1 + 2 + 2 + 3 = 10
3
1 2 3
Sample Output
10
Explanation
all subarrays [1] [1,2] [1,2,3] [2] [2,3] [3]
Sum of minimums : 1 + 1 + 1 + 2 + 2 + 3 = 10