#P1156E. Special Segments of Permutation
Special Segments of Permutation
Description
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.
Input
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.
Output
Print the number of special subsegments of the given permutation.
Samples
5
3 4 1 5 2
2
3
1 3 2
1
Note
Special subsegments in the first example are $[1, 5]$ and $[1, 3]$.
The only special subsegment in the second example is $[1, 3]$.