School
Description
John learned yesterday in school about permutations. His teacher defined a permutation of length $n$ as an array where each element from $1$ to $n$ occurs exactly once.
Being a curious little fellow he wonders for a given permutation $p$ of length $n$ how many pairs $(l, r), 1 \le l \le r \le n$ there are such that: $$ \forall i \in [l, r], min(p_l, p_r) \le p_i \le max(p_l, p_r) $$
The first line of the input contains one integer $n (1 \le n \le 5 \cdot 10^5)$ - the length of the permutation.
The second line contains $n$ integers $p_1, p_2,..., p_n (1 \le p_i \le n)$. It is guaranteed that the given numbers form a permutation of length n.
The output contains only one integer - the number of pairs.
Input
The first line of the input contains one integer $n (1 \le n \le 5 \cdot 10^5)$ - the length of the permutation.
The second line contains $n$ integers $p_1, p_2,..., p_n (1 \le p_i \le n)$. It is guaranteed that the given numbers form a permutation of length n.
Output
The output contains only one integer - the number of pairs.
5
1 3 2 4 5
12
Note
Some valid pairs are: $(1, 1)$, $(3, 5)$, $(1, 5)$, $(2, 3)$.