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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Stack;
//给你一个数列，问你有多少个区间符合条件：区间最左边的数加区间最右边的数等于区间的最大值。
//我最开始的想法是用线段树之类的维护区间最大值，然后查询，但如何快速查询不太会。。
//百度之后又看到大佬有用单调栈维护的，再遍历区间是否符合要求。这是第二次碰到单调栈了，单调栈的复杂度是O(n)
//这次终于把单调栈看懂了。可是怎么查询的还是不太懂。。
public class Main {
	static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static final int maxn=(int) (2e5+10);
	static int l[]=new int[maxn];//记录以i为最大值的从左到右的区间
	static int r[]=new int[maxn];//记录以i为最大值的从右到左的区间
	static int a[]=new int[maxn];//记录数列
	static int id[]=new int[maxn];//记录a数组该值的所对应的下标
	static int n,ans;
	static void find(int l,int r,int l1,int r1,int s){
		for(int i=l;i<=r;i++){
			int k=s-a[i];
			if(k>=1&&k<=n&&l1<=id[k]&&id[k]<=r1)
				ans++;
		}
	}
	public static void main(String[] args) {
		n=nextInt();
		for(int i=1;i<=n;i++){
			a[i]=nextInt();
			id[a[i]]=i;
		}
		Stack<Integer> s=new Stack<>();
		for(int i=1;i<=n;i++){
			while(!s.isEmpty()&&a[i]>a[s.peek()])
				s.pop();
			if(s.isEmpty())
				l[i]=0;
			else
				l[i]=s.peek();
			s.push(i);
		}
		while(!s.isEmpty()){
			s.pop();
		}
		for(int i=n;i>=1;i--){
			while(!s.isEmpty()&&a[i]>a[s.peek()])
				s.pop();
			if(s.isEmpty())
				r[i]=n+1;
			else
				r[i]=s.peek();
			s.push(i);
		}
		ans=0;
		for(int i=1;i<=n;i++){
			int ll=i-l[i]-1;//以i为最大值的左半边区间长度
			int rr=r[i]-i-1;//以i为最大值的由半边区间长度
			if(ll==0||rr==0){
				continue;
			}
			if(ll<rr){
				find(l[i]+1,i-1,i+1,r[i],a[i]);
			}else{
				find(i+1,r[i],l[i]+1,i-1,a[i]);
			}
		}
		System.out.println(ans);
	}
	static int nextInt(){
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int)st.nval;
	}
}
