← 返回题单

题单练习 ST表

← 上一题下一题 →

A6891 | $Max to the Right of Min$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为 $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}$ 的个数。

输入输出样例

输入 #1

3
1 2 3

输出 #1

输入 #2

6
5 3 6 1 4 2

输出 #2

输入 #3

10
5 1 6 2 8 3 4 10 9 7

输出 #3

C++ 编辑器

输入

输出