Alice has the following permutation A of integers from 1 to N, $(a_1,a_2,...,a_n)$. She wants to find sum of minimum values over all subarrays of A. i.e. find $\sum_{l=1}^{l=N}{\sum_{r=l}^{r=N}{min(a_l,a_{l+1},...,a_r)}}$

Input:

First line contains an integer N, the size of array A.

The second line consists of N space seperated integers denoting $(a_1,a_2,...,a_n)$

$(a_1,a_2,...,a_n)$ is a permutation of $(1,2,3..,.n)$

Output:

In a single line, output the answer.

Constraints:

$1\leq N \leq5*10^5$

$1\leq a_i\leq N$

Sample Tescases:

Input:

3

1 3 2

Output:

10

Explanation:

Answer=$min(a_1)+min(a_2)+min(a_3)+min(a_1,a_2)+min(a_2,a_3)+min(a_1,a_2,a_3)$

=1+3+2+1+2+1

=10