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.Scanner;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.AbstractCollection;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.LinkedList;

/**
 * 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;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        int N = 200005;
        int[] arr = new int[N];
        int[] pos = new int[N];
        int[] left = new int[N];
        int[] right = new int[N];

        public void solve(int testNumber, Scanner in1, PrintWriter out) {
            TaskE.FastReader in = new TaskE.FastReader();
            int n = in.nextInt();
            for (int i = 1; i <= n; i++) {
                arr[i] = in.nextInt();
                pos[arr[i]] = i;
            }
            LinkedList<Integer> st = new LinkedList<>();
            for (int i = 1; i <= n; i++) {
                while (!st.isEmpty() && st.peekLast() < arr[i]) {
                    int element = st.peekLast();
                    st.removeLast();
                    right[pos[element]] = i - 1;
                }
                st.addLast(arr[i]);
            }
            while (!st.isEmpty()) {
                int element = st.peekLast();
                st.removeLast();
                right[pos[element]] = n;
            }
            for (int i = n; i >= 1; i--) {
                while (!st.isEmpty() && st.peekLast() < arr[i]) {
                    int element = st.peekLast();
                    st.removeLast();
                    left[pos[element]] = i + 1;
                }
                st.addLast(arr[i]);
            }
            while (!st.isEmpty()) {
                int element = st.peekLast();
                st.removeLast();
                left[pos[element]] = 1;
            }
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                int p = pos[i];
                int l = left[pos[i]];
                int r = right[pos[i]];
                int sol1 = 0, sol2 = 0;
                for (int u = l, v = r; u != p && v != p; u++, v--) {
                    int z1 = i - arr[u], z2 = i - arr[v];
                    if (pos[z1] >= p && pos[z1] <= r)
                        sol1++;
                    if (pos[z2] <= p && pos[z2] >= l)
                        sol2++;
                }
                ans += Math.max(sol1, sol2);
            }
            out.println(ans);
        }

        static class FastReader {
            BufferedReader br;
            StringTokenizer st;

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

            String next() {
                while (st == null || !st.hasMoreElements()) {
                    try {
                        st = new StringTokenizer(br.readLine());
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                return st.nextToken();
            }

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

        }

    }
}

