310545: CF1849E. Max to the Right of Min

E. Max to the Right of Mintime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a permutation $p$ of length $n$ — an array, consisting of integers from $1$ to $n$, all distinct.

Let $p_{l,r}$ denote a subarray — an array formed by writing down elements from index $l$ to index $r$, inclusive.

Let $\mathit{maxpos}_{l,r}$ denote the index of the maximum element on $p_{l,r}$. Similarly, let $\mathit{minpos}_{l,r}$ denote the index of the minimum element on it.

Calculate the number of subarrays $p_{l,r}$ such that $\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$.

Input

The first line contains a single integer $n$ ($1 \le n \le 10^6$) — the number of elements in the permutation.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). All $p_i$ are distinct.

Output

Print a single integer — the number of subarrays $p_{l,r}$ such that $\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$.

ExamplesInput

3
1 2 3

Output

3

Input

6
5 3 6 1 4 2

Output

4

Input

10
5 1 6 2 8 3 4 10 9 7

Output

38

题目大意：
给定一个长度为n的排列p——一个由1到n的整数组成的数组，所有整数都是不同的。

定义p[l, r]为子数组——由索引l到索引r（包括r）的元素组成的数组。

定义maxpos_{l, r}为p_{l, r}上最大元素的索引。类似地，定义minpos_{l, r}为最小元素的索引。

计算满足maxpos_{l, r} > minpos_{l, r}的子数组p_{l, r}的数量。

输入数据格式：
第一行包含一个整数n（1 ≤ n ≤ 10^6）——排列中的元素数量。

第二行包含n个整数p_1, p_2, ..., p_n（1 ≤ p_i ≤ n）。所有p_i都是不同的。

输出数据格式：
打印一个整数——满足maxpos_{l, r} > minpos_{l, r}的子数组p_{l, r}的数量。题目大意： 给定一个长度为n的排列p——一个由1到n的整数组成的数组，所有整数都是不同的。 定义p[l, r]为子数组——由索引l到索引r（包括r）的元素组成的数组。 定义maxpos_{l, r}为p_{l, r}上最大元素的索引。类似地，定义minpos_{l, r}为最小元素的索引。 计算满足maxpos_{l, r} > minpos_{l, r}的子数组p_{l, r}的数量。 输入数据格式： 第一行包含一个整数n（1 ≤ n ≤ 10^6）——排列中的元素数量。 第二行包含n个整数p_1, p_2, ..., p_n（1 ≤ p_i ≤ n）。所有p_i都是不同的。 输出数据格式： 打印一个整数——满足maxpos_{l, r} > minpos_{l, r}的子数组p_{l, r}的数量。