A6891. 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}$。
设 $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$ 互不相同。
第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）。所有 $p_i$ 互不相同。
输出格式
输出一个整数，表示满足条件的子数组 $p_{l,r}$ 的个数。
输入输出样例
输入 #1
3 1 2 3
输出 #1
3
输入 #2
6 5 3 6 1 4 2
输出 #2
4
输入 #3
10 5 1 6 2 8 3 4 10 9 7
输出 #3
38