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 _{i = l}^{r} p_i. Please calculate the number of special subsegments.

Input

The first line contains one integer n (3 ≤ n ≤ 2 ⋅ 10^5).

The second line contains n integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ 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].
from sys import stdin
from itertools import repeat
def find(par, x):
    st = []
    pu = st.append
    while x != par[x]:
        pu(x)
        x = par[x]
    for y in st:
        par[y] = x
    return x
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, n))
    p = [0] * (n + 1)
    for i, x in enumerate(a):
        p[x] = i
    par = range(n)
    l = range(n)
    r = range(1, n + 1)
    ans = 0
    for x in xrange(1, n + 1):
        i = p[x]
        le = re = -1
        if i > 0 and a[i-1] < x:
            le = find(par, i - 1)
        if i < n - 1 and a[i+1] < x:
            re = find(par, i + 1)
        if le != -1 and re != -1:
            if r[le] - l[le] < r[re] - l[re]:
                for j in xrange(l[le], r[le]):
                    k = x - a[j]
                    if 1 <= k < x and l[re] <= p[k] < r[re]:
                        ans += 1
            else:
                for j in xrange(l[re], r[re]):
                    k = x - a[j]
                    if 1 <= k < x and l[le] <= p[k] < r[le]:
                        ans += 1
        if le != -1:
            par[le] = i
            l[i] = l[le]
        if re != -1:
            par[re] = i
            r[i] = r[re]
    print ans
main()
