排队

所有输入均从 queue.in 读取，所有输出均写入 queue.out。

时间限制：$1$ 秒。内存限制：$512$ MiB。

题目描述

$n$ 个人从左到右站成一排，依次编号为 $1,2,\ldots,n$。第 $i$ 个人的身高为 $a_i$，序列 $a$ 是 $1,2,\ldots,n$ 的一个排列。

每个人都已经记下了自己左边有多少个人比自己矮。现在选择一个非空区间 $[l,r]$，让编号为 $l,l+1,\ldots,r$ 的人离开，其余人的相对顺序保持不变。

如果留下来的每个人左边比自己矮的人数，都与离开前相同，就称这次选择合法。求有多少个合法的区间 $[l,r]$。

允许所有人都离开，此时这次选择也合法。

输入格式

第一行包含一个正整数 $n$。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示每个人的身高。

输出格式

输出一行一个整数，表示合法区间的数量。

样例

样例 1

输入：

3
3 1 2

输出：

4

合法的删除区间为 $[1,1]$、$[3,3]$、$[2,3]$ 和 $[1,3]$。

例如，若只让第 $2$ 个人离开，第 $3$ 个人左边比自己矮的人数会从 $1$ 变成 $0$，因此这种选择不合法。

附加样例

样例 2 见 $\texttt{down/queue2.in}$ 与 $\texttt{down/queue2.ans}$，满足测试点 $5\sim8$ 的限制。

样例 3 见 $\texttt{down/queue3.in}$ 与 $\texttt{down/queue3.ans}$，满足测试点 $9\sim10$ 的限制。

样例 4 见 $\texttt{down/queue4.in}$ 与 $\texttt{down/queue4.ans}$，满足测试点 $11\sim12$ 的限制。

样例 5 见 $\texttt{down/queue5.in}$ 与 $\texttt{down/queue5.ans}$，满足测试点 $13\sim20$ 的限制。

数据范围

对于所有测试点，$1\le n\le2\times10^5$，$1\le a_i\le n$，且 $a_1,a_2,\ldots,a_n$ 两两不同。

特殊性质 $A$：存在 $1\le p\le n$，使得 $a_1<a_2<\cdots<a_p$ 且 $a_p>a_{p+1}>\cdots>a_n$。

特殊性质 $B$：存在 $1\le p\le n$，使得 $a_1>a_2>\cdots>a_p$ 且 $a_p<a_{p+1}<\cdots<a_n$。上述两种性质均允许 $p=1$ 或 $p=n$。