For a permutation of the numbers from to , define as follows: for every pair with 1 \le i \le j \le n, consider the pair , where is the smallest of the numbers p_i, p_{i+1}, \ldots, p_j and is the largest of them. Then equals the number of distinct pairs among all \frac{n(n+1)}{2} pairs.
For example, consider the permutation (1, 3, 2).
For the pair , (min, max) = (1, 1)
For the pair , (min, max) = (1, 3)
For the pair , (min, max) = (1, 3)
For the pair , (min, max) = (3, 3)
For the pair , (min, max) = (2, 3)
For the pair , (min, max) = (2, 2)
There are distinct pairs in total, so f((1, 3, 2)) = 5.
Find for the given permutation (p_1, p_2, \ldots, p_n).
The first line contains one integer (1 \le n \le 2\cdot 10^5).
The second line contains integers p_1, p_2, \ldots, p_n (1 \le p_i \le n, all p_i are pairwise distinct) — the permutation of length .
Print .
Example 1
Example 2
Example 3
The first sample is explained in the statement.