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].
from collections import deque
from sys import stdin

def inv(perm):
	invp = [None] * len(perm)
	for i, p in enumerate(perm):
		invp[p] = i
	return invp

def main():
	n = int(stdin.readline())
	p = [int(x) - 1 for x in stdin.readline().split()]
	invp = inv(p)

	# Build auxiliary arrays
	nexL = [None] * n
	nexR = [None] * n
	q = deque()
	for i in range(0, n):
		while q and p[q[-1]] <= p[i]: 
			q.pop()
		nexL[i] = -1 if not q else q[-1]
		q.append(i)
	q.clear()
	for i in range(n - 1, -1, -1):
		while q and p[q[-1]] <= p[i]:
			q.pop()
		nexR[i] = n if not q else q[-1]
		q.append(i)

	# Solve
	res = 0
	for i in range(0, n):
		if i - nexL[i] < nexR[i] - i:
			for j in range(nexL[i] + 1, i):
				x = p[i] - p[j] - 1
				res += int(x >= 0 and i < invp[x] <= nexR[i])
		else:
			for j in range(i + 1, nexR[i]):
				x = p[i] - p[j] - 1
				res += int(x >= 0 and nexL[i] <= invp[x] < i)
	print(res)

main()