Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

divide and conquer

dsu

two pointers

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Special Segments of Permutation

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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]$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/25/2024 16:43:28 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|