E. Special Segments of Permutation
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

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.

Examples
Input
5
3 4 1 5 2
Output
2
Input
3
1 3 2
Output
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]$$$.