CF1849E.Max to the Right of Min

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} \gt \mathit{minpos}_{l,r}$.

给你一个长度为 $n$ 的排列 $p$ —— 一个由 $1$ 到 $n$ 的互不相同整数组成的数组。

记 $p_{l,r}$ 表示一个子数组——即由从索引 $l$ 到索引 $r$（含端点）的所有元素按顺序组成的数组。

记 $\mathit{maxpos}_{l,r}$ 表示 $p_{l,r}$ 中最大元素的索引。类似地，记 $\mathit{minpos}_{l,r}$ 表示 $p_{l,r}$ 中最小元素的索引。

请计算满足 $\mathit{maxpos}_{l,r} \gt \mathit{minpos}_{l,r}$ 的子数组 $p_{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.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 表示排列中元素的个数。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）。所有 $p_i$ 互不相同。

Print a single integer — the number of subarrays $p_{l,r}$ such that $\mathit{maxpos}_{l,r} \gt \mathit{minpos}_{l,r}$.

输出一个整数——满足 $\mathit{maxpos}_{l,r} \gt \mathit{minpos}_{l,r}$ 的子数组 $p_{l,r}$ 的个数。