← 返回题目列表

Codeforces · 1156/E

E. 排列的特殊段

中文机器翻译题面 查看原题

给你一个 $$$n$$$ 整数 $$$1$$$、$$$2$$$、...、$$$n$$$ 的排列 $$$p$$$(排列是一个数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个元素恰好出现一次)。

如果 $$$p_l + p_r = \max \limits_{i = l}^{r} p_i$$$,则我们称此排列的某些子段 $$$p[l, r]$$$ 为特殊。请计算特殊子段的数量。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$ ($$$1 \le p_i \le n$$$)。所有这些整数都是成对不同的。

输出

打印给定排列的特殊子段的数量。

示例

输入 #1

5
3 4 1 5 2

输出 #1

2

输入 #2

3
1 3 2

输出 #2

1

注意

第一个示例中的特殊子段是 $$$[1, 5]$$$ 和 $$$[1, 3]$$$。

第二个示例中唯一的特殊子段是 $$$[1, 3]$$$。