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 \limits_{i = l}^{r} p_i$. Please calculate the number of special subsegments.


-----Input-----

The first line contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $p_1$, $p_2$, ..., $p_n$ ($1 \le p_i \le 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]$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))

p = list(range(n + 1))
s = [set() for i in range(n + 1)]

def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

def union(x, y, cur):
    x, y = find(x), find(y)
    r = 0
    if len(s[x]) < len(s[y]):
        x, y = y, x
    for k in s[y]:
        r += cur - k in s[x]
    s[x] |= s[y]
    s[x].add(cur)
    p[y] = x
    return r

print(sum(union(i, i + 1, a[i]) for i in sorted(range(n), key=lambda i: a[i])))

n=int(input())
ns=[int(x) for x in input().split()]
# n=200000
# ns=[x+1 for x in range(n)]

"""
st=[[ns[i]]for i in range(n)]
for l in range(1,20):
    for i in range(0,n+10,2**l):
        if i+2**(l-1)<len(st):
            st[i].append(max(st[i][-1],st[i+2**(l-1)][-1]))
def get_sum(l,r):
    ans,i=st[l][0],1
    while l+2**i<=r and i<len(st[l]):
        ans=st[l][i]
        i+=1
    rr=l+2**(i-1)-1
    if rr>=r:
        return ans
    else:
        return max(ans,get_sum(rr+1,r))
"""
# print(time.time()-tm)
# import random as rd
#
# n=10000
# s=set()
# ns=[]
# for i in range(n):
#     s.add(i+1)
# for i in range(n):
#     x=rd.sample(s,1)
#     ns.append(x[0])
#     s.remove(x[0])
# print(ns)
# quit()
# ns=[5, 8, 4, 1, 6, 7, 2, 3]
# n=len(ns)

maxx=max(ns)+10
lst=[None]*n
nxt=[None]*n
tmp=[(-1,maxx)]
mp=[False]*n
wh=[None]*(n+1)
for i in range(n):
    c=ns[i]
    while tmp[-1][1]<=c:
        tmp.pop()
    lst[i]=tmp[-1][0]
    tmp.append((i,c))
tmp=[(n,maxx)]
for i in range(n):
    i=n-i-1
    c=ns[i]
    while tmp[-1][1]<=c:
        tmp.pop()
    nxt[i]=tmp[-1][0]
    tmp.append((i,c))
lm={}
for i in range(n):
    lm[(lst[i]+1,nxt[i]-1)]=ns[i]
# print(lm)


for i in range(n):
    wh[ns[i]]=i

def check(i,m,lm):
    f=ns[m]-ns[i]
    f=wh[f]
    if lm[0]<=f<=lm[1]:
        return True
    return False
# print(wh)
ans=0
rec=[(0,n-1)]

def get():
    if len(rec)==0:
        return False
    l,r=rec.pop()
    if r-l+1<=2:
        return True
    nonlocal ans
    x=lm[(l,r)]
    lc=wh[x]
    if lc<(l+r)//2:
        for i in range(l,lc):
            c=ns[i]
            c=ns[lc]-c
            c=wh[c]
            if lc<=c<=r:
                ans+=1
    else:
        for i in range(lc+1,r+1):
            c=ns[i]
            c=ns[lc]-c
            c=wh[c]
            if l<=c<=lc:
                ans+=1
    rec.append((l,lc-1))
    rec.append((lc+1,r))
while len(rec)>0:
    get()
print(ans)
quit()




get(0,n-1)
print(ans)
quit()


x=n
while x>=1:
    lc=wh[x]
    mp[lc]=True
    l,r=lc-1,lc+1
    while l>lst[lc] and (not mp[l]) :
        l-=1
    while r<nxt[lc] and (not mp[r]):
        r+=1
    if lc-l<r-lc:
        for i in range(l+1,lc):
            if check(i,lc,(lc+1,r-1)):
                ans+=1
    else:
        for i in range(lc+1,r):
            if check(i,lc,(l+1,lc-1)):
                ans+=1
    x-=1
print(ans)
#
# # print(lst)
# # print(nxt)
#
# def std(n,ns):
#     ans=0
#     for i in range(n):
#         for j in range(i,n):
#             if max(ns[i:j+1])==ns[i]+ns[j]:
#                 ans+=1
#     return ans
# print(ns)
# print(std(n,ns))
#
# if ans==std(n,ns):
#     print('True')
# else:
#     print('False')


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))


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()

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()

# ez
import math
pown = 1
ind = []
f = []
pw = []
 
def get(l,r):
    x = pw[r - l + 1]
    if f[r][x] > f[l+p2[x]-1][x]:
        return f[r][x]
    return f[l + p2[x] - 1][x]

def solve(x,y):
    if y <= x:
        return 0
    p = get(x,y)
    if y - p[1] <= p[1] - x:
        cur = 0
        for i in range(p[1] , y + 1):
            if ind[p[0] - a[i]] >= x and ind[p[0] - a[i]] <= p[1]:
                cur = cur + 1
        return cur + solve(x , p[1] - 1) + solve(p[1] + 1 , y)
    else:
        cur = 0
        for i in range(x , p[1] + 1):
            if ind[p[0] - a[i]] >= p[1] and ind[p[0] - a[i]] <= y:
                cur = cur + 1
        return cur + solve(x , p[1] - 1) + solve(p[1] + 1 , y)

n = int(input())
 
for i in range(0 , 200005):
    pw.append(0)
p2 = []
p2.append(1)
for i in range(1,20):
    p2.append(p2[i - 1] * 2)
for i in range(0,18):
    for j in range(p2[i] , p2[i + 1]):
        if j <= 200000:
            pw[j] = i
 
arr = [int(i) for i in input().split()]
a = []
a.append(0)
for i in range(0 , n):
    a.append(arr[i])
for i in range(0 , n+1):
    ind.append(0)
 
for i in range(1 , n + 1):
    ind[a[i]] = i
for i in range(1 , 200005):
    ad = []
    for j in range(0 , 19):
        ad.append((0 , 0))
    f.append(ad)
 
for i in range(1 , n + 1):
    f[i][0] = (a[i] , i)
    for j in range(1 , 18):
        f[i][j] = f[i][j - 1]
        if i - p2[j] >= 0 and f[i - p2[j - 1]][j - 1] > f[i][j]:
            f[i][j] = f[i - p2[j - 1]][j - 1]
ans = 0

q = []

q.append((1 , n))
maxind = 1
num = 0
while num < maxind:
    x = q[num][0]
    y = q[num][1]
    #print(x , y)
    p = get(x,y)
    #print(p)
    if y - p[1] <= p[1] - x:
        for i in range(p[1] , y + 1):
            #print(i , a[i])
            if ind[p[0] - a[i]] >= x and ind[p[0] - a[i]] <= p[1]:
                ans += 1
    else:
        for i in range(x , p[1] + 1):
            if ind[p[0] - a[i]] >= p[1] and ind[p[0] - a[i]] <= y:
                ans += 1
    if x < p[1] - 1:
        q.append((x , p[1] - 1))
        maxind += 1
    if y > p[1] + 1:
        q.append((p[1] + 1 , y))
        maxind += 1
    num += 1
    #print(num , maxind)

print(ans)


n=int(input())
a=[int(x) for x in input().split()]
def Count_Segment(a,n):
	ans=0
	upto=[0]*(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
 
print(Count_Segment(a,n))
        
           
       


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)

mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    N = int(input())
    P = list(map(int, input().split()))

    idx = [0] * (N+1)
    for i, p in enumerate(P):
        idx[p] = i+1
    bit = Bit(N)
    ans = 0
    for p in range(N, 0, -1):
        i = idx[p]
        k = bit.sum(i)
        r = bit.lower_bound(k+1)
        l = bit.lower_bound(k)
        nl = i - l - 1
        nr = r - i - 1
        if nl < nr:
            for j in range(l+1, i):
                q = P[j-1]
                if i < idx[p - q] < r:
                    ans += 1
        else:
            for j in range(i+1, r):
                q = P[j-1]
                if l < idx[p - q] < i:
                    ans += 1
        bit.add(i, 1)
        #print(l, r)
    print(ans)


def __starting_point():
    main()

__starting_point()

n=int(input())
a=list(map(int,input().split()))
if a==[i+1 for i in range(n)]:print(0);return
if a==[i+1 for i in range(n)][::-1]:print(0);return
p=[0]*(n+1)
p[0]=-1
for i in range(n):p[a[i]]=i
num=2**(n-1).bit_length()
def segfunc(x,y):
  if a[x]<a[y]:return y
  else:return x
seg=[0]*(2*num-1)
for i in range(n):seg[i+num-1]=i
for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
def update(i,x):
  i+=num-1;seg[i]=x
  while i:i=(i-1)//2;seg[i]=segfunc(seg[i*2+1],seg[i*2+2])
def query(l,r):
  l+=num-1;r+=num-2
  if l==r:return seg[l]
  s=seg[l];l+=1
  while r-l>1:
    if ~l%2:s=segfunc(seg[l],s)
    if r%2:s=segfunc(seg[r],s);r-=1
    l//=2;r=(r-1)//2
  if l==r:return segfunc(s,seg[l])
  return segfunc(s,segfunc(seg[l],seg[r]))
def f(l,r):
  if r-l<2:return 0
  maxi=query(l,r+1)
  ma=a[maxi]
  ans=f(l,maxi-1)+f(maxi+1,r)
  if maxi-l<r-maxi:
    for i in range(l,maxi):
      if maxi<p[ma-a[i]]<=r:ans+=1
  else:
    for i in range(maxi+1,r+1):
      if l<=p[ma-a[i]]<maxi:ans+=1
  return ans
print(f(0,n-1))