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].
n = int(input())
a = list(map(int,input().split()))
dc = {a[i]:i for i in range(n)}
stack = []
mxr = [n]*(n+1)
mxl = [-1]*(n+1)
for i,x in enumerate(a):
  if i == 0:
    stack.append(x)
    continue
  while stack and stack[-1] < x:
    y = stack.pop()
    mxr[y] = i
  stack.append(x)
stack = []
for i,x in enumerate(a[::-1]):
  i = n-1-i
  if i == n-1:
    stack.append(x)
    continue
  while stack and stack[-1] < x:
    y = stack.pop()
    mxl[y] = i
  stack.append(x)
ans = 0
for i in range(n,0,-1):
  idx = dc[i]
  l = mxl[i]
  r = mxr[i]
  if idx-l-1 > r-idx-1:
    for j in range(idx+1,r):
      if l < dc[i-a[j]] < idx:
        ans += 1
  else:
    for j in range(idx-1,l,-1):
      if idx < dc[i-a[j]] < r:
        ans += 1
print(ans)