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 int []getLeft(int []a,boolean rev){
		Stack<Integer> stack =new Stack();
		int n=a.length;
		int []ans=new int [n],revAns=new int [n];
		for(int i=0;i<n;i++) {
			while(!stack.isEmpty() && a[i]>a[stack.peek()])
				stack.pop();
			ans[i]=stack.isEmpty()?0:stack.peek()+1;
			revAns[n-1-i]= n-1-ans[i];
			stack.push(i);
		}
		
		return rev?revAns:ans;
	}
	
		public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int n=sc.nextInt();
		int []a=new int [n],rev=new int [n],pos=new int [n+1];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
			rev[n-1-i]=a[i];
			pos[a[i]]=i;
		}
		long ans=0;
		int []left=getLeft(a, false),right=getLeft(rev, true);
		for(int i=0;i<n;i++) {
			int max=a[i];
			int l=left[i],r=right[i];
			if(i-l<r-i) 
				for(int j=l;j<i;j++) {
					int p=pos[max-a[j]];
					if(p>i && p<=r)
						ans++;
				}
			
			else
				for(int j=i+1;j<=r;j++) {
					int p=pos[max-a[j]];
					if(p<i && p>=l) {
						ans++;
					}
				}
				
			
			
		}
		out.println(ans);
		out.close();

	}

	static class edge {
		int v, t;

		edge(int a, int b) {
			v = a;
			t = b;
		}
	}

	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());
		}

	}

}