codeforces#P1849E. Max to the Right of Min
Max to the Right of Min
Description
You are given a permutation $p$ of length $n$ — an array, consisting of integers from $1$ to $n$, all distinct.
Let $p_{l,r}$ denote a subarray — an array formed by writing down elements from index $l$ to index $r$, inclusive.
Let $\mathit{maxpos}_{l,r}$ denote the index of the maximum element on $p_{l,r}$. Similarly, let $\mathit{minpos}_{l,r}$ denote the index of the minimum element on it.
Calculate the number of subarrays $p_{l,r}$ such that $\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$.
The first line contains a single integer $n$ ($1 \le n \le 10^6$) — the number of elements in the permutation.
The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). All $p_i$ are distinct.
Print a single integer — the number of subarrays $p_{l,r}$ such that $\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$.
Input
The first line contains a single integer $n$ ($1 \le n \le 10^6$) — the number of elements in the permutation.
The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). All $p_i$ are distinct.
Output
Print a single integer — the number of subarrays $p_{l,r}$ such that $\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$.
3
1 2 3
6
5 3 6 1 4 2
10
5 1 6 2 8 3 4 10 9 7
3
4
38