Farmer John's NN cows (N≤3×105**)N≤3×105) have heights 1,2,…,N1,2,…,N. One day, the cows are standing in a line in some order playing frisbee; let h1…hNh1…hN denote the heights of the cows in this order (so the hh's are a permutation of 1…N1…N).Two cows at positions ii and jj in the line can successfully throw the frisbee back and forth if and only if every cow between them has height lower than min(hi,hj**)min(hi,hj).

Please compute the sum of distances between all pairs of locations i<ji<j at which there resides a pair of cows that can successfully throw the frisbee back and forth. The distance between locations ii and jj is j−i+1j−i+1.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains a single integer NN. The next line of input contains h1**…hN**h1…hN, separated by spaces.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the sum of distances of all pairs of locations at which there are cows that can throw the frisbee back and forth. Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

7
4 3 1 2 5 6 7

SAMPLE OUTPUT:

24

The pairs of successful locations in this example are as follows:

(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)

SCORING

• Test cases 1-3 satisfy N≤5000N≤5000.
• Test cases 4-11 satisfy no additional constraints.