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].
def Count_Segment(a,n):
	ans=0
	upto=[False]*(n+1)
	for i in range(1,n-1):
		if a[i]>a[i-1] and a[i]>a[i+1]:
			curr=a[i]
			j=i-1
			while j>=0 and a[j]<curr:
				upto[a[j]]=curr
				j-=1

			j=i+1
			while j<n and a[j]<curr:
				if upto[curr-a[j]]==curr:
					ans+=1
				j+=1

	return ans

n=int(input())
a=list(map(int,input().split( )))
print(Count_Segment(a,n))
