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.io.*;
import java.util.*;
public class Main {
    public static int n, next;
    public static int[] arr, pos, tree;
    public static int next(int n) {
        int i = 1;
        while (i < n) {
            i *= 2;
        }
        return i;
    }
    public static int max(int i, int l, int r, int L, int R) {
        if (l <= L && R <= r) {
            return tree[i];
        }
        if (l > R || L > r) {
            return 0;
        }
        int mid = (L + R) / 2;
        return Math.max(max(i * 2, l, r, L, mid), max(i * 2 + 1, l, r, mid + 1, R));
    }
    public static int max(int l, int r) {
        return max(1, l, r, 0, next - 1);
    }
    public static int real(int l, int r) {
        int max = 0;
        for (int i = l; i <= r; i++) {
            max = Math.max(max, arr[i]);
        }
        return max;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(rd.readLine());
        next = next(n);
        arr = new int[n];
        pos = new int[n + 1];
        String[] line = rd.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(line[i]);
            pos[arr[i]] = i;
        }
        tree = new int[next * 2];
        for (int i = 0; i < n; i++) {
            tree[next + i] = arr[i];
        }
        for (int i = next - 1; i >= 1; i--) {
            tree[i] = Math.max(tree[i * 2], tree[i * 2 + 1]);
        }
        TreeSet<Integer> crit = new TreeSet<>();
        crit.add(-1);
        crit.add(n);
        int res = 0;
        for (int i = n; i >= 1; i--) {
            int p = pos[i];
            int a = crit.floor(p);
            int b = crit.ceiling(p);
            if (Math.abs(p - a) < Math.abs(p - b)) {
                for (int j = p - 1; j > a; j--) {
                    int elem = arr[j];
                    if (elem > i) break;
                    int match = i - elem;
                    if (match > 0 && pos[match] > p && max(1, j, pos[match], 0, next - 1) == i) {
                        res++;
                    }
                }
            } else {
                for (int j = p + 1; j < b; j++) {
                    int elem = arr[j];
                    if (elem > i) break;
                    int match = i - elem;
                    if (match > 0 && pos[match] < p && max(1, pos[match], j, 0, next - 1) == i) {
                        res++;
                    }
                }
            }
            crit.add(p);
        }
        System.out.println(res);
    }
}