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].

import java.util.*;
import java.io.*;

public class Main1 {
    public static void main(String args[]) { new Main1().WORK(); }

    Scanner in = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    final int N = (int)(2e5+10);

    int[] p = new int[N];
    HashSet<Integer>[] S = new HashSet[N];

    int find(int x) {
        if(x == p[x]) return x;
        p[x] = find(p[x]);
        return p[x];
    }

    void merge(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return;
        if(S[x].size() > S[y].size()) {
            int t = x; x = y; y = t;
        }
        S[y].addAll(S[x]);
        S[x].clear();
        p[x] = y;
    }

    int query(int x, int y, int mx) {
        int ret = 0;
        x = find(x); y = find(y);
        if(S[x].size() > S[y].size()) {
            int t = x; x = y; y = t;
        }
        for(int t:S[x]) {
            if(S[y].contains(mx-t)) ret++;
        }
        return ret;
    }

    void WORK() {
        int n = in.nextInt();
        boolean[] vis = new boolean[n+5];
        int[] a = new int[n+1], pos = new int[n+5];
        for(int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
            pos[a[i]] = i;
            p[i] = i;
            S[i] = new HashSet<>();
            S[i].add(a[i]);
        }
        long ans = 0;
        for(int i = 1; i <= n; i++) {
            if(vis[pos[i]-1] && vis[pos[i]+1])
                ans += query(pos[i]-1, pos[i]+1, i);
            if(vis[pos[i]-1]) merge(pos[i]-1, pos[i]);
            if(vis[pos[i]+1]) merge(pos[i]+1, pos[i]);
            vis[pos[i]] = true;
        }
        out.println(ans);
        out.flush();
    }
}