Question
Sum of Minimas
In a distant kingdom, there's a magical array of N unique integers. The wise sages of the land have given you a quest: to find the sum of the smallest element from every possible subarray (continuous segment) of this array.
Each subarray has its own story, and the key to solving this challenge lies in discovering the minimum element of each one and adding them all together. Only then will you unlock the true wisdom of the array. Your mission is to compute this grand total!
Each subarray has its own story, and the key to solving this challenge lies in discovering the minimum element of each one and adding them all together. Only then will you unlock the true wisdom of the array. Your mission is to compute this grand total!
Input
The first line of input contains a single space-separated integer N, denoting the size of the array.
The second line of input contains N space-separated integers.
Constraints
2 ≤ N ≤ 100000
1 ≤ Arr[i] ≤ 1000000000
The second line of input contains N space-separated integers.
Constraints
2 ≤ N ≤ 100000
1 ≤ Arr[i] ≤ 1000000000
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
Explaination
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
Explaination
all subarrays [1] [1,2] [1,2,3] [2] [2,3] [3]
Sum of minimums : 1 + 1 + 1 + 2 + 2 + 3 = 10