CF1849E Max to the Right of Min

给定一个长度为 $n$ 的排列 $p$ —— 一个由 $1$ 到 $n$ 的整数构成的数组，所有元素互不相同。 设 $p_{l,r}$ 表示子数组 —— 由下标 $l$ 到 $r$（包含两端）组成的数组。 设 $\mathit{maxpos}_{l,r}$ 表示 $p_{l,r}$ 中最大元素的下标。同理，$\mathit{minpos}_{l,r}$ 表示 $p_{l,r}$ 中最小元素的下标。 请计算有多少个子数组 $p_{l,r}$ 满足 $\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$。

第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示排列的长度。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）。所有 $p_i$ 互不相同。

输出一个整数，表示满足条件的子数组 $p_{l,r}$ 的个数。

由 ChatGPT 4.1 翻译