题目描述

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

输入 #1

3
1 2 3

输出 #1

3

输入输出样例 #2

输入 #2

6
5 3 6 1 4 2

输出 #2

4

输入输出样例 #3

输入 #3

10
5 1 6 2 8 3 4 10 9 7

输出 #3

38