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 A {

	static ArrayList<Integer>[]adj;
	static SparseTable st;
	static int []a,left,right;
	static HashSet[]sets;
	static int build(int l,int r) {
		if(l>r)
			return 0;
		if(l==r)
			return a[l];
		int maxIdx= st.query(l, r);
		int value=a[maxIdx];
		left[value]=build(l,maxIdx-1);
		right[value]=build(maxIdx+1,r);
		return value;
		
	}
	static int solve(int u) {
		if(u==0)
			return 0;
		int l=left[u],r=right[u];
		int ans=solve(l) + solve(r);
		HashSet<Integer> small;
		
		if(sets[l].size()<sets[r].size()) {
			small=l==0?new HashSet<Integer>():sets[l];
			sets[u]=r==0?new HashSet<Integer>():sets[r];
		}
		else
		{
			small=r==0?new HashSet<Integer>():sets[r];
			sets[u]=l==0?new HashSet<Integer>():sets[l];
		}
		for(int x:small) {
			if(sets[u].contains(u-x))
				ans++;
		}
		for(int x:small)
			sets[u].add(x);
		sets[u].add(u);
		return ans;
	}
		public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int n=sc.nextInt();
		a=new int [n];
		left=new int [n+1];
		right=new int [n+1];
		sets=new HashSet[n+1];
		sets[0]=new HashSet();
		for(int i=0;i<n;i++)
			a[i]=sc.nextInt();
		st=new SparseTable();
		build(0,n-1);
		out.println(solve(n));
		out.close();

	}

	static class SparseTable{
		int [][]table;
		int []log;
		SparseTable(){
			
			int n=a.length;
			log=new int [n+1];
			for(int i=2;i<=n;i++)
				log[i]=log[i>>1]+1;
			table=new int [log[n]+1][n];
			for(int i=0;i<n;i++)
				table[0][i]=i;
			for(int i=1,len=2;i<table.length;i++,len<<=1) {
				for(int j=0;j+len<=n;j++) {
					int i1=table[i-1][j],i2=table[i-1][j+len/2];
					table[i][j]=a[i1]>a[i2]?i1:i2;
				}
			}
			
		}
		int query(int l,int r) {
			int len=r-l+1;
			int lg=log[len];
			int i1=table[lg][l];
			int i2=table[lg][r+1-(1<<lg)];
			return a[i1]>a[i2]?i1:i2;
		}
	}
	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

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

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

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

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

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

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

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

	}

}