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.*;
import java.util.*;

public class Main implements Runnable{
    public static void main(String[] args){
        //new Thread(null,new Main(),"Thread-1",1024*1024*10).start();
        new Main().run();
    }
    int n,a[],pos[],l[],r[];
    private void solve() throws Exception {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        n=in.nextInt();
        a=new int[n+1];
        pos=new int[n+1];
        l=new int[n+1];
        r=new int[n+1];
        for(int i=1;i<=n;i++){
            a[i]=in.nextInt();
            pos[a[i]]=i;
        }
        Stack<Integer> st=new Stack<>();
        for(int i=1;i<=n;i++){
            if(st.isEmpty()||a[st.peek()]>a[i])st.push(i);
            else {
                while(!st.isEmpty()&&a[st.peek()]<a[i]){
                    r[a[st.pop()]]=i-1;
                }
                st.push(i);
            }
        }
        while(!st.isEmpty())r[a[st.pop()]]=n;

        for(int i=n;i>=1;i--){
            if(st.isEmpty()||a[st.peek()]>a[i])st.push(i);
            else {
                while(!st.isEmpty()&&a[st.peek()]<a[i]){
                    l[a[st.pop()]]=i+1;
                }
                st.push(i);
            }
        }
        while(!st.isEmpty())l[a[st.pop()]]=1;
        int ans=0;
        for(int i=n;i>=1;i--){
            if(r[i]-pos[i]<pos[i]-l[i]){
                for(int j=pos[i]+1;j<=r[i];j++){
                    int p=pos[i-a[j]];
                    if(p>=l[i]&&p<pos[i])ans++;
                }
            }else {
                for(int j=l[i];j<pos[i];j++){
                    int p=pos[i-a[j]];
                    if(p>pos[i]&&p<=r[i])ans++;
                }
            }
        }
        out.println(ans);
        out.flush();
    }
    @Override
    public void run() {
        try {
            solve();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    void shuffle(int[]a,int l,int r){
        Random rnd=new Random();
        for (int i=r; i>l+1; i--) {
            int j=rnd.nextInt(i),tmp=a[j];
            a[j]=a[i-1];
            a[i-1]=tmp;
        }
    }
    void shuffle(Object[]a,int l,int r){
        Random rnd=new Random();
        for (int i=r; i>l+1; i--) {
            int j=rnd.nextInt(i);
            Object tmp=a[j];
            a[j]=a[i-1];
            a[i-1]=tmp;
        }
    }
    void shuffle(long[]a,int l,int r){
        Random rnd=new Random();
        for (int i=r; i>l+1; i--) {
            int j=rnd.nextInt(i);
            long tmp=a[j];
            a[j]=a[i-1];
            a[i-1]=tmp;
        }
    }
    class InputReader{
        StreamTokenizer tokenizer;
        public InputReader(InputStream stream){
            tokenizer=new StreamTokenizer(new BufferedReader(new InputStreamReader(stream)));
            tokenizer.ordinaryChars(33,126);
            tokenizer.wordChars(33,126);
        }
        public String next() throws IOException {
            tokenizer.nextToken();
            return tokenizer.sval;
        }
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        public boolean hasNext() throws IOException {
            int res=tokenizer.nextToken();
            tokenizer.pushBack();
            return res!=tokenizer.TT_EOF;
        }
    }
}