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.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;

import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.util.Arrays.sort;

public class Main {
    FastScanner in;
    PrintWriter out;

    private void solve() throws IOException {
        int n = in.nextInt();
        int[] p = new int[n], pos = new int[n];
        for (int i = 0; i < n; i++)
            pos[p[i] = in.nextInt() - 1] = i;

        int[] l = new int[n], r = new int[n];
        int[] st = new int[n];
        int ss = 0;

        for (int i = 0; i < n; i++) {
            while (ss > 0 && st[ss - 1] < p[i])
                ss--;
            l[i] = ss == 0 ? -1 : pos[st[ss - 1]];
            st[ss++] = p[i];
        }

        ss = 0;
        for (int i = n - 1; i >= 0; i--) {
            while (ss > 0 && st[ss - 1] < p[i])
                ss--;
            r[i] = ss == 0 ? n : pos[st[ss - 1]];
            st[ss++] = p[i];
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
            if (i - l[i] < r[i] - i)
                for (int j = l[i] + 1; j < i; j++)
                    ans += p[i] > p[j] && pos[p[i] - p[j] - 1] > i && pos[p[i] - p[j] - 1] < r[i] ? 1 : 0;
            else
                for (int j = i + 1; j < r[i]; j++)
                    ans += p[i] > p[j] && pos[p[i] - p[j] - 1] < i && pos[p[i] - p[j] - 1] > l[i] ? 1 : 0;
        out.println(ans);
    }

    class FastScanner {
        StringTokenizer st;
        BufferedReader br;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

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

        boolean hasNext() throws IOException {
            return br.ready() || (st != null && st.hasMoreTokens());
        }

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

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

        boolean hasNextLine() throws IOException {
            return br.ready();
        }
    }

    private void run() throws IOException {
        in = new FastScanner(System.in); // new FastScanner(new FileInputStream(".in"));
        out = new PrintWriter(System.out); // new PrintWriter(new FileOutputStream(".out"));

        solve();

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

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}