← 返回题目列表

Codeforces · 1849/E

E. 最大值在最小值的右侧

中文机器翻译题面 查看原题

给您一个长度为 $$$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} > \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}$$$ 的数量,使得 $$$\mathit{maxpos}_{l,r} > \mathit{minpos}_{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