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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner();
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt();
        int[] p = new int[n];
        int[] idx = new int[n + 1];
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextInt();
            idx[p[i]] = i;
        }
        long ans = 0;
        TreeSet<Integer> pos = new TreeSet<>();
        for (int i = n; i >= 0; i--) {
            int left = 0, right = n - 1, j = idx[i];
            Integer hi = pos.higher(j), lo = pos.lower(j);
            if (hi != null) right = hi - 1;
            if (lo != null) left = lo + 1;
            pos.add(j);
            if (right - j < j - left) {
                //move right
                for (int k = j + 1; k <= right; k++) {
                    int need = i - p[k];
                    if (idx[need] >= left && idx[need] <= j) ans++;
                }
            } else {
                //move left
                for (int k = j - 1; k >= left; k--) {
                    int need = i - p[k];
                    if (idx[need] >= j && idx[need] <= right) ans++;
                }

            }
        }
        out.println(ans);
        out.flush();
        out.close();
    }

    static class Scanner {
        BufferedReader br;
        StringTokenizer st;

        Scanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}