Problems
Simple sum
Simple sum
Nikhat arranged the numbers 1, 2, ... , n in ascending order. Later Hussein came and swapped some of these numbers. Now we have some mixed sequence p_1, p_2, ..., p_n of numbers from 1 to n.
Calculate the following sum for this sequence:
\sum_{l = 1}^N \sum_{r = l}^N min(p_l, p_{l+1}, ..., p_r)
Simply put, you need to find the sum of all the minimum numbers in all subsequences of a given sequence.
The min
function finds the minimum of the given numbers.
Input data
The first line contains one integer n(1 ≤ n ≤ 10^5) - the number of numbers in the sequence. The second line contains n integers p_i(1 ≤ p_i ≤ n) - elements of the sequence.
Output data
Print the required amount corresponding to the given sequence.
Examples
Input example #1
3 2 1 3
Output example #1
9
Input example #2
4 1 2 3 4
Output example #2
20