后缀数

给定一个 $1$ 到 $n$ 的排列 $a$，下标从 $1$ 开始。对于任意满足 $1\le l<r\le n$ 的 $l,r$，考虑连续子段 $a_l,a_{l+1},\ldots,a_r$。

称该连续子段为候选后缀数，当且仅当满足以下条件：

1. $a_l$ 是该子段的最小值，$a_r$ 是该子段的最大值，且 $a_r-a_l=r-l$。这等价于该子段中的值恰为 $a_l,a_l+1,\ldots,a_r$。
2. 设值 $a_r-1$ 在排列中的位置为 $p$，则 $2p\le l+r$。
3. 设值 $a_l+1$ 在排列中的位置为 $q$，则 $2q\ge l+r$。

如果一个候选后缀数不真包含任何其他候选后缀数，则称其为后缀数。

求排列中后缀数的数量。不同的后缀数可以相交。

输入格式

第一行输入一个整数 $n$，表示排列的长度。

第二行输入 $n$ 个整数，表示排列 $a$，相邻整数之间用一个空格分隔。

输出格式

输出一个整数 $ans$，表示后缀数的总数。

样例输入

6
1 2 3 4 5 6

样例输出

5

数据范围

• $2\le n\le 10^6$；
• $a$ 是 $1$ 到 $n$ 的一个排列。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

6
1 2 3 4 5 6

输出

5