Question
The Array’s Wisdom Quest
In the ancient realm of Numeria, the High Council of Elders has presented you with a unique challenge. You are given a magical array of N distinct numbers, each holding a secret power. To unlock the ultimate knowledge of Numeria, you must decipher the array’s wisdom by finding the sum of the smallest element in every possible subarray (a continuous sequence) within the array. Each subarray reveals a hidden truth, and only by calculating the sum of these smallest elements will you unveil the full power of the array.
Your quest is to compute this mystical sum and prove your worth to the Council.
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
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