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: HARD
Tags: Spanning trees

Data structures

Amortized analysis

Divide and conquer
Skill types: Amortized analysis

Data structures

Starter code:

Solutions:
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(ans)
main()


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]
	p = get(x, y)
	if y - p[1] <= p[1] - x:
		for i in range(p[1], y + 1):
			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(ans)


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


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


n = int(input())
ns = [int(x) for x in input().split()]
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]
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
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
	global 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)


import io, os
input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
n = ii()
a = li()
p = list(range(n + 1))
s = [set() for i in range(n + 1)]
idx = list(range(n))
idx.sort(key=lambda i: a[i])

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))
	assert x != 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
ans = 0
for i in idx:
	ans += union(i, i + 1, a[i])
print(ans)


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)


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


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)


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