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].
//created by Whiplash99
import java.io.*;
import java.util.*;
public class E
{
    private static int[] a,inv;
    private static int calc(int pos, int l, int r, int start, int end)
    {
        int count=0, idx;
        for(int i=l;i<=r;i++)
        {
            idx=inv[a[pos]-a[i]];
            if(start<=idx&&idx<=end) count++;
        }
        return count;
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int i,N;
        String[] s;

        N=Integer.parseInt(br.readLine().trim());
        s=br.readLine().trim().split(" ");
        a=new int[N];
        for(i=0;i<N;i++) a[i]=Integer.parseInt(s[i]);

        ArrayDeque<Integer> stack=new ArrayDeque<>();
        int[] prev=new int[N], next=new int[N];

        for(i=N-1;i>=0;i--) //previous greater
        {
            while (!stack.isEmpty()&&a[i]>a[stack.peek()]) prev[stack.pop()]=i;
            stack.push(i);
        }
        while (!stack.isEmpty()) prev[stack.pop()]=-1;

        for(i=0;i<N;i++) //next greater
        {
            while (!stack.isEmpty()&&a[i]>a[stack.peek()]) next[stack.pop()]=i;
            stack.push(i);
        }
        while (!stack.isEmpty()) next[stack.pop()]=N;

        inv=new int[N+5];
        for(i=0;i<N;i++) inv[a[i]]=i; //inverse permutation, i.e., storing positions.

        int ans=0;
        for(i=0;i<N;i++) //loved the observation!!
        {
            int l=prev[i], r=next[i];
            if(i-l==1||r-i==1) continue;

            if(i-l<r-i) ans+=calc(i,l+1,i-1, i+1,r-1);
            else ans+=calc(i,i+1,r-1,l+1,i-1);
        }
        System.out.println(ans);
    }
}