Frisbee Toss

Farmer John's N cows have distinct heights of 1,2,…,N. One day the cows line up in some order to play frisbee; let h₁, h₂, …, h_N denote the heights of the cows in that order (i.e. h is a permutation of 1,…,N).

Two cows at positions i and j (with i < j) can successfully toss the frisbee back and forth if and only if every cow between them has height less than \(\min(h_i, h_j)\) (in \(\LaTeX\) format). The distance between positions i and j is defined as j-i+1.

Calculate the total sum of distances for all pairs of positions (i, j) (i < j) such that the two cows can successfully toss the frisbee.

Note: \(N \le 3 \times 10^5\).

inputFormat

The first line contains a single integer N, the number of cows.

The second line contains N distinct integers, a permutation of 1, 2, ..., N, representing the heights h₁, h₂, ..., h_N.

outputFormat

Output a single integer, the total sum of distances (j - i + 1) over all pairs (i, j) (i < j) that can successfully toss the frisbee.

sample

3
2 1 3

7