You are given a permutation ~a~ of the integers from ~1~ to ~N~. You want to find

$$\displaystyle \displaystyle \sum_{l=1}^{N}{\sum_{r=l}^{N}{\min(a_l,a_{l+1},\ldots,a_r)}} $$

In other words, let ~M_{l,r} = \min(a_l,a_{l+1},\ldots,a_r)~. You want to find the sum of ~M_{l,r}~ for all ~1 \le l \le r \le N~.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 2 \times 10^5)~.

The next line will contain ~N~ space-separated integers, ~a_i~ ~(1 \le a_i \le N)~. ~a~ is guaranteed to be pairwise distinct. In other words, ~a_i~ forms a permutation.

Output Specification

The answer to the problem. Note that the answer may not fit in a 32-bit integer.

Sample Input 1

3
2 1 3

Sample Output 1

9

Sample Input 2

4
1 3 2 4

Sample Output 2

19

Sample Input 3

8
5 4 8 1 2 6 7 3

Sample Output 3

85