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 sys; input = sys.stdin.readline
import heapq as hq
n = int(input())
a = list(map(int, input().split()))
place = [0]*(n+1)
for i in range(n):
	place[a[i]] = i
par = [-1]*n
nums = [{} for i in range(n)]
def find(x):
	if x == par[x]: return x
	par[x] = find(par[x])
	return par[x]
def comb(x, y):
	x, y = find(x), find(y)
	if len(nums[x]) < len(nums[y]):
		x, y = y, x
	par[y] = x
	for num in nums[y]: nums[x][num] = 1
a.sort()
ans = 0
for x in a:
	cur = place[x]
	par[cur] = cur
	nums[cur][x] = 1
	if cur-1 >= 0 and cur+1 < n and par[cur-1] != -1 and par[cur+1] != -1:
		l, r = find(cur-1), find(cur+1)
		l, r = nums[l], nums[r]
		r_list = []
		for num in sorted(r.keys()): r_list.append(num)
		p2 = len(r_list) - 1
		for num in sorted(l.keys()):
			while p2 >= 0 and num + r_list[p2] > x:
				p2 -= 1
			ans += p2 >= 0 and num + r_list[p2] == x
	if cur-1 >= 0 and par[cur-1] != -1:
		comb(cur-1, cur)
	if cur+1 < n and par[cur+1] != -1:
		comb(cur+1, cur)
print(ans)