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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.ni();
            int[] p = in.na(n);
            int[] idx = new int[n + 1];
            for (int i = 0; i < n; i++) {
                idx[p[i]] = i;
            }
            TreeSet<Integer> blocked = new TreeSet<>();
            blocked.add(-1);
            blocked.add(n);
            int ans = 0;
            for (int max = n; max > 0; --max) {
                int pos = idx[max];
                int right = blocked.higher(pos);
                int left = blocked.lower(pos);
//            System.out.print("max = " + max);
//            System.out.print(" left = " + left);
//            System.out.println(" right = " + right);
                if (right - pos - 1 < pos - left - 1) {
                    for (int i = pos + 1; i < right; i++) {
                        if (p[i] > max)
                            throw new RuntimeException();
                        int pairPos = idx[max - p[i]];
                        if (left < pairPos && pairPos < pos) {
                            ans++;
                        }
                    }
                } else {
                    for (int i = left + 1; i < pos; i++) {
                        if (p[i] > max)
                            throw new RuntimeException();
                        int pairPos = idx[max - p[i]];
                        if (pos < pairPos && pairPos < right) {
                            ans++;
                        }
                    }
                }
                blocked.add(pos);
            }
            out.println(ans);
        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String ns() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int ni() {
            return Integer.parseInt(ns());
        }

        public int[] na(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = ni();
            return a;
        }

    }
}

