306166: CF1156E. Special Segments of Permutation

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Special Segments of Permutation

题意翻译

给定一个长度为 $n$ 的排列 $p$,求有多少区间 $[l,r]$ 满足,$p_l+p_r=\max\limits_{i=l}^r\{p_i\}$。

题目描述

You are given a permutation $ p $ of $ n $ integers $ 1 $ , $ 2 $ , ..., $ n $ (a permutation is an array where each element from $ 1 $ to $ n $ occurs exactly once). Let's call some subsegment $ p[l, r] $ of this permutation special if $ p_l + p_r = \max \limits_{i = l}^{r} p_i $ . Please calculate the number of special subsegments.

输入输出格式

输入格式


The first line contains one integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ). The second line contains $ n $ integers $ p_1 $ , $ p_2 $ , ..., $ p_n $ ( $ 1 \le p_i \le n $ ). All these integers are pairwise distinct.

输出格式


Print the number of special subsegments of the given permutation.

输入输出样例

输入样例 #1

5
3 4 1 5 2

输出样例 #1

2

输入样例 #2

3
1 3 2

输出样例 #2

1

说明

Special subsegments in the first example are $ [1, 5] $ and $ [1, 3] $ . The only special subsegment in the second example is $ [1, 3] $ .

Input

题意翻译

给定一个长度为 $n$ 的排列 $p$,求有多少区间 $[l,r]$ 满足,$p_l+p_r=\max\limits_{i=l}^r\{p_i\}$。

加入题单

上一题 下一题 算法标签: