给您一个长度为 $$$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