AtCoder Beginner Contest 140 - Second Sum

Given is a permutation P of \{1, 2, \ldots, N\}.
For a pair (L, R) (1 \le L \lt R \le N), let X_{L, R} be the second largest value among P_L, P_{L+1}, \ldots, P_R.
Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

-----Constraints-----
 -  2 \le N \le 10^5 
 -  1 \le P_i \le N 
 -  P_i \neq P_j  (i \neq j)
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
P_1 P_2 \ldots P_N

-----Output-----
Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

-----Sample Input-----
3
2 3 1

-----Sample Output-----
5

X_{1, 2} = 2, X_{1, 3} = 2, and X_{2, 3} = 1, so the sum is 2 + 2 + 1 = 5.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
N = int(input())
P = list(map(int, input().split()))
left_bigger = [0] + [i for i in range(N + 1)]
right_bigger = [i + 1 for i in range(N + 1)] + [N + 1]
E = [(v, i + 1) for (i, v) in enumerate(P)]
E.sort()
ans = 0
for (v, i) in E:
	l0 = left_bigger[i]
	l1 = left_bigger[l0]
	r0 = right_bigger[i]
	r1 = right_bigger[r0]
	ans += ((r1 - r0) * (i - l0) + (r0 - i) * (l0 - l1)) * v
	left_bigger[r0] = l0
	right_bigger[l0] = r0
print(ans)


import sys
from heapq import heappush, heappop
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, *P) = map(int, read().split())
	idx = [0] * (N + 1)
	for (i, p) in enumerate(P):
		idx[p] = i
	left = list(range(-1, N)) + [-1]
	right = list(range(1, N + 1)) + [N, N]
	ans = 0
	for n in range(1, N + 1):
		i = idx[n]
		l1 = left[i]
		l2 = left[l1]
		r1 = right[i]
		r2 = right[r1]
		ans += n * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
		left[r1] = l1
		right[l1] = r1
	print(ans)
	return
main()


import sys
input = sys.stdin.readline
n = int(input())
a = [int(j) for j in input().split()]
ans = 0
ind = [0] * (n + 1)
for i in range(n):
	ind[a[i]] = i + 1
l = [0] + list(range(n + 1))
r = list(range(1, n + 2)) + [n + 1]
for i in range(1, n + 1):
	l1 = l[ind[i]]
	l0 = l[l1]
	r0 = r[ind[i]]
	r1 = r[r0]
	ans += ((l1 - l0) * (r0 - ind[i]) + (r1 - r0) * (ind[i] - l1)) * i
	l[r0] = l1
	r[l1] = r0
print(ans)


import sys
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(buff_readline())

def read_int_n():
	return list(map(int, buff_readline().split()))

def read_float():
	return float(buff_readline())

def read_float_n():
	return list(map(float, buff_readline().split()))

def read_str():
	return readline().strip()

def read_str_n():
	return readline().strip().split()

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

class SegmentTree:

	def __init__(self, array, operator, identity_element):
		_len = len(array)
		self.__op = operator
		self.__size = 1 << (_len - 1).bit_length()
		self.__tree = [identity_element] * self.__size + array + [identity_element] * (self.__size - _len)
		self.__ie = identity_element
		for i in range(self.__size - 1, 0, -1):
			self.__tree[i] = operator(self.__tree[i * 2], self.__tree[i * 2 + 1])

	def update(self, i, v):
		i += self.__size
		self.__tree[i] = v
		while i:
			i //= 2
			self.__tree[i] = self.__op(self.__tree[i * 2], self.__tree[i * 2 + 1])

	def query(self, l, r):
		l += self.__size
		r += self.__size
		ret = self.__ie
		while l < r:
			if l & 1:
				ret = self.__op(ret, self.__tree[l])
				l += 1
			if r & 1:
				r -= 1
				ret = self.__op(ret, self.__tree[r])
			l //= 2
			r //= 2
		return ret

def slv(N, P):
	lst = SegmentTree([0] * (N + 1), max, 0)
	rst = SegmentTree([N + 1] * (N + 1), min, N + 1)
	pi = [(p, i + 1) for (i, p) in enumerate(P)]
	pi.sort(reverse=True)
	lst.update(pi[0][1], pi[0][1])
	rst.update(pi[0][1], pi[0][1])
	ans = 0
	for (p, i) in pi[1:]:
		l = lst.query(0, i + 1)
		ll = lst.query(0, l)
		r = rst.query(i, N + 1)
		rr = rst.query(r + 1, N + 1)
		lst.update(i, i)
		rst.update(i, i)
		c = 0
		c += max(0, l - ll) * (r - i)
		c += max(0, rr - r) * (i - l)
		ans += c * p
	return ans

def main():
	N = read_int()
	P = read_int_n()
	print(slv(N, P))
main()


N = int(input())
(*P,) = map(int, input().split())
LL = [0] + [i for i in range(N + 1)]
RR = [i + 1 for i in range(N + 1)] + [N + 1]
E = [(v, i + 1) for (i, v) in enumerate(P)]
E.sort()
ans = 0
for (v, i) in E:
	l0 = LL[i]
	l1 = LL[l0]
	r0 = RR[i]
	r1 = RR[r0]
	(LL[RR[i]], RR[LL[i]]) = (LL[i], RR[i])
	ans += ((r1 - r0) * (i - l0) + (r0 - i) * (l0 - l1)) * v
print(ans)


def solve():
	N = int(input())
	Ps = list(map(int, input().split()))

	def makeBIT(numEle):
		numPow2 = 2 ** (numEle - 1).bit_length()
		data = [0] * (numPow2 + 1)
		return (data, numPow2)

	def addValue(iA, A):
		iB = iA + 1
		while iB <= numPow2:
			data[iB] += A
			iB += iB & -iB

	def getSum(iA):
		iB = iA + 1
		ans = 0
		while iB > 0:
			ans += data[iB]
			iB -= iB & -iB
		return ans
	(data, numPow2) = makeBIT(N)
	iPs = list(range(N))
	iPs.sort(key=lambda iP: Ps[iP])
	ans = 0
	for iP in reversed(iPs):
		v = getSum(iP)
		Bs = []
		for x in range(v - 1, v + 3):
			if x <= 0:
				L = -1
			elif getSum(numPow2 - 1) < x:
				L = N
			else:
				maxD = numPow2.bit_length() - 1
				L = 0
				S = 0
				for d in reversed(range(maxD)):
					if S + data[L + (1 << d)] < x:
						S += data[L + (1 << d)]
						L += 1 << d
			Bs.append(L)
		num = (Bs[1] - Bs[0]) * (Bs[2] - iP) + (iP - Bs[1]) * (Bs[3] - Bs[2])
		ans += Ps[iP] * num
		addValue(iP, 1)
	print(ans)
solve()


from bisect import bisect_left, bisect_right, insort_right

class SquareSkipList:

	def __init__(self, values=None, sorted_=False, square=1000, seed=42):
		inf = float('inf')
		self.rand_y = seed
		self.square = square
		if values is None:
			self.layer1 = []
			self.layer0 = [[]]
		else:
			self.layer1 = layer1 = []
			self.layer0 = layer0 = []
			if not sorted_:
				values.sort()
			rand_depth = self.rand_depth
			l0 = []
			for v in values:
				if rand_depth():
					layer0.append(l0)
					l0 = []
					layer1.append(v)
				else:
					l0.append(v)
			layer0.append(l0)
		self.layer1.append(inf)

	def rand_depth(self):
		y = self.rand_y
		y ^= y << 13 & 4294967295
		y ^= y >> 17
		y ^= y << 5 & 4294967295
		self.rand_y = y
		return y % self.square == 0

	def add(self, x):
		(layer1, layer0) = (self.layer1, self.layer0)
		if self.rand_depth():
			idx1 = bisect_right(layer1, x)
			layer1.insert(idx1, x)
			layer0_idx1 = layer0[idx1]
			idx0 = bisect_right(layer0_idx1, x)
			layer0.insert(idx1 + 1, layer0_idx1[idx0:])
			del layer0_idx1[idx0:]
		else:
			idx1 = bisect_right(layer1, x)
			insort_right(layer0[idx1], x)

	def remove(self, x):
		(layer1, layer0) = (self.layer1, self.layer0)
		idx1 = bisect_left(layer1, x)
		if layer1[idx1] == x:
			del layer1[idx1]
			layer0[idx1] += layer0[idx1 + 1]
			del layer0[idx1 + 1]
		else:
			layer0_idx1 = layer0[idx1]
			del layer0_idx1[bisect_left(layer0_idx1, x)]

	def bisect_left(self, x):
		(layer1, layer0) = (self.layer1, self.layer0)
		idx1 = bisect_left(layer1, x)
		res = layer1[idx1]
		if res == x:
			return res
		layer0_idx1 = layer0[idx1]
		if layer0_idx1:
			idx0 = bisect_left(layer0_idx1, x)
			if idx0 == len(layer0_idx1):
				return res
			else:
				return layer0_idx1[idx0]
		else:
			return res

	def search_higher(self, x):
		(layer1, layer0) = (self.layer1, self.layer0)
		idx1 = bisect_right(layer1, x)
		layer0_idx1 = layer0[idx1]
		idx0 = bisect_right(layer0_idx1, x)
		if idx0 == len(layer0_idx1):
			return layer1[idx1]
		return layer0_idx1[idx0]

	def search_lower(self, x):
		(layer1, layer0) = (self.layer1, self.layer0)
		idx1 = bisect_left(layer1, x)
		layer0_idx1 = layer0[idx1]
		idx0 = bisect_left(layer0_idx1, x)
		if idx0 == 0:
			return layer1[idx1 - 1]
		return layer0_idx1[idx0 - 1]

	def pop(self, idx):
		(layer1, layer0) = (self.layer1, self.layer0)
		s = -1
		for (i, l0) in enumerate(layer0):
			s += len(l0) + 1
			if s >= idx:
				break
		if s == idx:
			layer0[i] += layer0[i + 1]
			del layer0[i + 1]
			return layer1.pop(i)
		else:
			return layer0[i].pop(idx - s)

	def print(self):
		print(self.layer1)
		print(self.layer0)

def main():
	n = int(input())
	p = list(map(int, input().split()))
	idx = [0] * n
	for i in range(0, n):
		idx[i] = i
	idx.sort(key=lambda i: -p[i])
	ssl = SquareSkipList()
	ssl.add(-1)
	ssl.add(n)
	ans = 0
	for i in idx:
		nex = ssl.search_higher(i)
		nexnex = ssl.search_higher(nex)
		pre = ssl.search_lower(i)
		prepre = ssl.search_lower(pre)
		if prepre != float('inf'):
			ans += p[i] * (pre - prepre) * (nex - i)
		if nexnex != float('inf'):
			ans += p[i] * (i - pre) * (nexnex - nex)
		ssl.add(i)
	print(ans)
main()


n = int(input())
p = list(map(int, input().split()))
l = [0] + [i for i in range(n + 1)]
r = [i + 1 for i in range(n + 1)] + [n + 1]
d = [0] * (n + 1)
for i in range(n):
	d[p[i]] = i + 1
ans = 0
for i in range(1, n + 1):
	ans += ((r[r[d[i]]] - r[d[i]]) * (d[i] - l[d[i]]) + (r[d[i]] - d[i]) * (l[d[i]] - l[l[d[i]]])) * i
	(l[r[d[i]]], r[l[d[i]]]) = (l[d[i]], r[d[i]])
print(ans)


import bisect

class SqrtSet:

	def __init__(self, block_limit=201):
		self.key = []
		self.child = [[]]
		self.block_limit = block_limit

	def search_lower(self, key):
		if key is None:
			return None
		ret = None
		i = bisect.bisect_left(self.key, key)
		if i != 0:
			ret = self.key[i - 1]
		block = self.child[i]
		i = bisect.bisect_left(block, key)
		if i != 0:
			ret = block[i - 1]
		return ret

	def search_higher(self, key):
		if key is None:
			return None
		ret = None
		i = bisect.bisect_right(self.key, key)
		if i != len(self.key):
			ret = self.key[i]
		block = self.child[i]
		i = bisect.bisect_right(block, key)
		if i != len(block):
			ret = block[i]
		return ret

	def insert(self, key):
		i = bisect.bisect(self.key, key)
		block = self.child[i]
		bisect.insort(block, key)
		if len(block) == self.block_limit:
			sep = self.block_limit // 2
			self.key.insert(i, block[sep])
			self.child.insert(i + 1, block[sep + 1:])
			self.child[i] = block[:sep]

	def dump(self):
		for b in self.child:
			print(len(b), end=' ')
		print('')

def main():
	n = int(input())
	p = list(map(int, input().split()))
	idx = [0] * n
	for i in range(0, n):
		idx[i] = i
	idx.sort(key=lambda i: -p[i])
	t = SqrtSet()
	t.insert(-10)
	t.insert(n + 10)
	ans = 0
	for i in range(n):
		if i == 0:
			t.insert(idx[i])
			continue
		ri = t.search_higher(idx[i])
		pri = t.search_higher(ri)
		if pri == None:
			pri = n
			ri = n
		if pri == n + 10:
			pri = n
		le = t.search_lower(idx[i])
		ple = t.search_lower(le)
		if ple == None:
			if le == -10:
				le = -1
				ple = -1
		if ple == -10:
			ple = -1
		ans += (n - i) * ((le - ple) * (ri - idx[i]) + (pri - ri) * (idx[i] - le))
		t.insert(idx[i])
	print(ans)
main()


def argsort(a):
	return list(map(lambda z: z[1], sorted(zip(a, range(len(a))))))
N = int(input())
P = list(map(int, input().split()))
a = argsort(P)
left = [i for i in range(N)]
right = [i for i in range(N)]
result = 0
for i in range(1, N):
	k = a[i - 1]
	extend_left = k - 1 >= 0 and P[k - 1] < i
	extend_right = k + 1 < N and P[k + 1] < i
	if extend_left and extend_right:
		L = left[k - 1]
		R = right[k + 1]
	elif extend_left:
		L = left[k - 1]
		R = k
	elif extend_right:
		R = right[k + 1]
		L = k
	else:
		L = k
		R = k
	right[L] = R
	left[R] = L
	if L - 1 >= 0:
		if L - 2 >= 0 and P[L - 2] < i:
			LL = left[L - 2]
		else:
			LL = L - 1
		result += (L - 1 - LL + 1) * (R - k + 1) * i
	if R + 1 < N:
		if R + 2 < N and P[R + 2] < i:
			RR = right[R + 2]
		else:
			RR = R + 1
		result += (RR - (R + 1) + 1) * (k - L + 1) * i
print(result)


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

class BIT(object):

	def __init__(self, A, dot, e, inv=None):
		n = len(A)
		self.__n = n
		self.__dot = dot
		self.__e = e
		self.__inv = inv
		self.__node = ['$'] + A
		for i in range(1, n + 1):
			j = i + (i & -i)
			if j <= n:
				self.__node[j] = dot(self.__node[i], self.__node[j])

	def add(self, i, w=1):
		i += 1
		while i <= self.__n:
			self.__node[i] = self.__dot(self.__node[i], w)
			i += i & -i

	def sum(self, i):
		res = self.__e
		while i > 0:
			res = self.__dot(res, self.__node[i])
			i -= i & -i
		return res

	def range_sum(self, l, r):
		assert self.__inv
		return self.__inv(self.sum(r), self.sum(l))

	def bisect_left(self, w, increase=True):
		n = self.__n
		k = 2 ** (self.__n - 1).bit_length()
		res = 0
		now = self.__e
		while k:
			if res + k <= n and self.__dot(now, self.__node[res + k]) < w and increase:
				now = self.__dot(now, self.__node[res + k])
				res += k
			elif res + k <= n and self.__dot(now, self.__node[res + k]) > w and (not increase):
				now = self.__dot(now, self.__node[res + k])
				res += k
			k //= 2
		return res

def resolve():
	n = int(input())
	A = list(map(int, input().split()))
	idx = [0] * n
	for (i, a) in enumerate(A):
		idx[a - 1] = i
	from operator import add
	bit = BIT([0] * n, add, 0)
	ans = 0
	for k in range(n, 0, -1):
		i = idx[k - 1]
		bit.add(i)
		s = bit.sum(i + 1)
		l0 = bit.bisect_left(s - 1) - (s <= 1)
		l1 = bit.bisect_left(s - 2) - (s <= 2)
		r0 = bit.bisect_left(s + 1)
		r1 = bit.bisect_left(s + 2)
		ans += k * ((i - l0) * (r1 - r0) + (l0 - l1) * (r0 - i))
	print(ans)
resolve()


N = int(input())
P = [None] + [int(x) for x in input().split()]
id_list = [None] * (N + 1)
for (i, x) in enumerate(P[1:], 1):
	id_list[x] = i

class BIT:

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

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

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

	def search(self, x):
		i = 0
		s = 0
		step = 1 << N.bit_length() - 1
		while step:
			if i + step <= N and s + self.tree[i + step] < x:
				i += step
				s += self.tree[i]
			step >>= 1
		return i + 1

def main():
	bit = BIT(N)
	ans = 0
	for x in range(N, 0, -1):
		idx = id_list[x]
		L = bit.sum(idx)
		bit.add(idx)
		R = N - x - L
		ll = bit.search(L - 1) if L >= 2 else 0
		l = bit.search(L) if L >= 1 else 0
		r = bit.search(L + 2) if R >= 1 else N + 1
		rr = bit.search(L + 3) if R >= 2 else N + 1
		coef = 0
		if l != 0:
			coef += (l - ll) * (r - idx)
		if r != 0:
			coef += (rr - r) * (idx - l)
		ans += x * coef
	print(ans)
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
n = int(input())
p = list(map(lambda x: int(x) - 1, input().split()))

def init(bit, values):
	for (i, v) in enumerate(values):
		add(bit, i + 1, v)

def query(bit, i):
	res = 0
	while i > 0:
		res += bit[i]
		i -= i & -i
	return res

def add(bit, i, x):
	if i == 0:
		raise RuntimeError
	while i <= len(bit) - 1:
		bit[i] += x
		i += i & -i
	return

def index(bit, v):
	i = 0
	n = len(bit) - 1
	k = 1 << (n - 1).bit_length()
	while k > 0:
		if i + k < n + 1 and bit[i + k] < v:
			v -= bit[i + k]
			i += k
		k //= 2
	if v == 1:
		return i + 1
	else:
		return n + 1
ind = [None] * n
for (i, num) in enumerate(p):
	ind[num] = i
bit = [0] * (n + 1)
l = [None] * n
l2 = [None] * n
r = [None] * n
r2 = [None] * n
for num in range(n - 1, -1, -1):
	i = query(bit, ind[num])
	if i == 0:
		l[ind[num]] = -1
		l2[ind[num]] = -1
	elif i == 1:
		l[ind[num]] = index(bit, i) - 1
		l2[ind[num]] = -1
	else:
		l[ind[num]] = index(bit, i) - 1
		l2[ind[num]] = index(bit, i - 1) - 1
	r[ind[num]] = index(bit, i + 1) - 1
	r2[ind[num]] = index(bit, i + 2) - 1
	add(bit, ind[num] + 1, 1)
ans = 0
for (i, (num, li, li2, ri, ri2)) in enumerate(zip(p, l, l2, r, r2)):
	v = 0
	if li >= 0:
		v += (ri - i) * (li - li2)
	if ri < n:
		v += (i - li) * (ri2 - ri)
	ans += v * (num + 1)
print(ans)


def rotate(nd, d):
	c = nd[d]
	if d:
		e = c[1]
		nd[1] = c[0]
		c[0] = nd
	else:
		e = c[0]
		nd[0] = c[1]
		c[1] = nd
	r = c[4] = nd[4]
	nd[4] = r - (e[4] if e else 0) - 1
	return c
root = None

def insert(val, pri):
	global root
	st = []
	dr = []
	x = root
	while x:
		st.append(x)
		if x[2] == val:
			return
		d = x[2] < val
		dr.append(d)
		x = x[d]
	nd = [None, None, val, pri, 1]
	while st:
		x = st.pop()
		d = dr.pop()
		x[d] = nd
		x[4] += 1
		if x[3] >= nd[3]:
			break
		rotate(x, d)
	else:
		root = nd
	for x in st:
		x[4] += 1

def __delete(nd):
	st = []
	dr = []
	while nd[0] or nd[1]:
		l = nd[0]
		r = nd[1]
		d = l[3] <= r[3] if l and r else l is None
		st.append(rotate(nd, d))
		dr.append(d ^ 1)
	nd = x = None
	while st:
		nd = x
		x = st.pop()
		d = dr.pop()
		x[d] = nd
		x[4] -= 1
	return x

def delete(val):
	global root
	x = root
	st = []
	y = None
	while x:
		if val == x[2]:
			break
		y = x
		d = x[2] < val
		st.append(y)
		x = x[d]
	else:
		return
	if y:
		y[d] = __delete(x)
		for x in st:
			x[4] -= 1
	else:
		root = __delete(x)

def find(val):
	global root
	x = root
	while x:
		if val == x[2]:
			return 1
		x = x[x[2] < val]
	return 0

def search1(val):
	global root
	x = root
	ans = -1
	while x:
		if val == x[2]:
			return val
		if val > x[2]:
			ans = max(ans, x[2])
			if x[1] == None:
				return ans
			else:
				x = x[1]
		if val < x[2]:
			if x[0] == None:
				return ans
			else:
				x = x[0]
	return ans

def search2(val):
	global root, N
	x = root
	ans = N
	while x:
		if val == x[2]:
			return val
		if val > x[2]:
			if x[1] == None:
				return ans
			else:
				x = x[1]
		if val < x[2]:
			ans = min(ans, x[2])
			if x[0] == None:
				return ans
			else:
				x = x[0]
	return ans
import random
N = int(input())
P = list(map(int, input().split()))
dic = {key: -1 for key in range(1, N + 1)}
for i in range(0, N):
	dic[P[i]] = i
answer = 0
for i in range(0, N):
	k = N - i
	l1 = search1(dic[k])
	l2 = search1(l1 - 1)
	r1 = search2(dic[k])
	r2 = search2(r1 + 1)
	answer += k * (dic[k] - l1) * (r2 - r1) + k * (l1 - l2) * (r1 - dic[k])
	insert(dic[k], random.randint(1, 100000))
print(answer)


N = int(input())
P_id = [0] * (N + 1)
for (index, p) in enumerate(map(int, input().split())):
	P_id[p] = index
left_next_index = list(range(-1, N - 1)) + ['うんこ', -1]
right_next_index = list(range(1, N + 1)) + [N, 'うんこ']
res = 0
for p in range(1, N):
	l1 = left_next_index[P_id[p]]
	l2 = left_next_index[l1]
	r1 = right_next_index[P_id[p]]
	r2 = right_next_index[r1]
	res += p * ((l1 - l2) * (r1 - P_id[p]) + (P_id[p] - l1) * (r2 - r1))
	left_next_index[r1] = l1
	right_next_index[l1] = r1
print(res)


import time
import random

class TreapNode:

	def __init__(self, key, pri):
		self.left = None
		self.right = None
		self.key = key
		self.pri = pri

class Treap:

	def __init__(self):
		self.root = None

	def search_lower(self, key):
		if key == None:
			return None
		ptr = self.root
		ret = None
		while ptr is not None:
			pk = ptr.key
			if pk < key:
				ret = pk
				ptr = ptr.right
			else:
				ptr = ptr.left
		return ret

	def search_higher(self, key):
		if key == None:
			return None
		ptr = self.root
		ret = None
		while ptr is not None:
			pk = ptr.key
			if pk > key:
				ret = pk
				ptr = ptr.left
			else:
				ptr = ptr.right
		return ret

	def insert(self, key):
		pri = random.randrange(0, 2 ** 25)
		ptr = self.root
		elem = TreapNode(key, pri)
		if ptr is None or ptr.pri < pri:
			self.root = elem
		else:
			while True:
				if key < ptr.key:
					left = ptr.left
					if left is None or left.pri < pri:
						ptr.left = elem
						ptr = left
						break
					ptr = left
				else:
					right = ptr.right
					if right is None or right.pri < pri:
						ptr.right = elem
						ptr = right
						break
					ptr = right
		left = elem
		right = elem
		while ptr is not None:
			if key < ptr.key:
				right.left = ptr
				right = ptr
				ptr = ptr.left
			else:
				left.right = ptr
				left = ptr
				ptr = ptr.right
		left.right = None
		right.left = None
		(elem.left, elem.right) = (elem.right, elem.left)

	def dump(self):
		self.__dump(self.root, 0)

	def __dump(self, idx, dep):
		if idx is not None:
			self.__dump(idx.right, dep + 1)
			for _ in range(0, dep):
				print('   ', end='')
			print([idx.key, idx.pri])
			self.__dump(idx.left, dep + 1)

def main():
	n = int(input())
	p = list(map(int, input().split()))
	idx = [0] * n
	for i in range(0, n):
		idx[i] = i
	idx.sort(key=lambda i: -p[i])
	t = Treap()
	t.insert(-1)
	t.insert(n)
	ans = 0
	for i in idx:
		nex = t.search_higher(i)
		nexnex = t.search_higher(nex)
		pre = t.search_lower(i)
		prepre = t.search_lower(pre)
		if prepre != None:
			ans += p[i] * (pre - prepre) * (nex - i)
		if nexnex != None:
			ans += p[i] * (i - pre) * (nexnex - nex)
		t.insert(i)
	print(ans)
main()


from time import time
from statistics import median
from bisect import bisect_left, bisect_right
from random import random, sample

class TwoLayerSet:

	def __init__(self, p):
		self.top = []
		self.bottom = [[]]
		self.p = p

	def insert(self, key):
		(top, bottom) = (self.top, self.bottom)
		top_i = bisect_left(top, key)
		if top_i != len(top) and key == top[top_i]:
			return False
		block = bottom[top_i]
		block_i = bisect_left(block, key)
		if block_i != len(block) and key == block[block_i]:
			return False
		if random() < self.p:
			top.insert(top_i, key)
			bottom[top_i] = block[block_i:]
			bottom.insert(top_i, block[:block_i])
		else:
			block.insert(block_i, key)
		return True

	def erase(self, key):
		(top, bottom) = (self.top, self.bottom)
		top_i = bisect_left(top, key)
		if top_i != len(top) and key == top[top_i]:
			top.pop(top_i)
			bottom[top_i].extend(bottom.pop(top_i + 1))
			return True
		block = bottom[top_i]
		block_i = bisect_left(block, key)
		if block_i != len(block) and key == block[block_i]:
			block.pop(block_i)
			return True
		return False

	def less(self, key):
		if key is None:
			return None
		top = self.top
		top_i = bisect_left(top, key)
		block = self.bottom[top_i]
		block_i = bisect_left(block, key)
		if block_i != 0:
			return block[block_i - 1]
		if top_i != 0:
			return top[top_i - 1]
		return None

	def less_equal(self, key):
		top = self.top
		top_i = bisect_right(top, key)
		block = self.bottom[top_i]
		block_i = bisect_right(block, key)
		if block_i != 0:
			return block[block_i - 1]
		if top_i != 0:
			return top[top_i - 1]
		return None

	def greater(self, key):
		if key is None:
			return None
		top = self.top
		top_i = bisect_right(top, key)
		block = self.bottom[top_i]
		block_i = bisect_right(block, key)
		if block_i != len(block):
			return block[block_i]
		if top_i != len(top):
			return top[top_i]
		return None

	def greater_equal(self, key):
		top = self.top
		top_i = bisect_left(top, key)
		block = self.bottom[top_i]
		block_i = bisect_left(block, key)
		if block_i != len(block):
			return block[block_i]
		if top_i != len(top):
			return top[top_i]
		return None

def main():
	n = int(input())
	p = list(map(int, input().split()))
	idx = [0] * n
	for i in range(0, n):
		idx[i] = i
	idx.sort(key=lambda i: -p[i])
	t = TwoLayerSet(1 / 1000)
	t.insert(-1)
	t.insert(n)
	ans = 0
	for i in idx:
		nex = t.greater(i)
		nexnex = t.greater(nex)
		pre = t.less(i)
		prepre = t.less(pre)
		if prepre != None:
			ans += p[i] * (pre - prepre) * (nex - i)
		if nexnex != None:
			ans += p[i] * (i - pre) * (nexnex - nex)
		t.insert(i)
	print(ans)
main()


class BinaryIndexedTree:

	def __init__(self, size):
		size = 1 << (size - 1).bit_length()
		self.data = [0] * (size + 1)
		self.size = size

	def add(self, i, w):
		i += 1
		while i <= self.size:
			self.data[i] += w
			i += i & -i

	def sum(self, i):
		result = 0
		while i > 0:
			result += self.data[i]
			i -= i & -i
		return result
	__getitem__ = sum

	def lower_bound(self, v):
		(s, pos) = (0, 0)
		N = self.size
		k = N
		while k > 0:
			i = pos + k
			if i <= N:
				x = s + self.data[i]
				if x < v:
					s = x
					pos = i
			k >>= 1
		return pos

def naive(P):

	def it():
		for i in range(len(P) - 1):
			for j in range(i + 1, len(P)):
				yield sorted(P[i:j + 1])[-2]
	return sum(it())

def solve(P):

	def it():
		bit = BinaryIndexedTree(len(P))
		for (cnt, (v, i)) in enumerate(sorted(((v, i) for (i, v) in enumerate(P)), reverse=True)):
			bit.add(i, 1)
			c = bit.sum(i)
			low1 = -1 if c <= 0 else bit.lower_bound(c)
			low2 = -1 if c <= 1 else bit.lower_bound(c - 1)
			up1 = len(P) if c > cnt - 1 else bit.lower_bound(c + 2)
			up2 = len(P) if c > cnt - 2 else bit.lower_bound(c + 3)
			yield (v * ((up1 - i) * (low1 - low2) + (i - low1) * (up2 - up1)))
	return sum(it())
N = int(input())
P = list(map(int, input().split()))
print(solve(P))


N = int(input())
P = list(map(int, input().split()))
index_lst = [0] * N
for (index, i) in enumerate(P):
	index_lst[i - 1] = index
left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]
ans = 0
for i in range(1, N):
	index = index_lst[i - 1]
	l1 = left_next_Index[index]
	l2 = left_next_Index[l1]
	r1 = right_next_Index[index]
	r2 = right_next_Index[r1]
	ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 - l2))
	left_next_Index[r1] = l1
	right_next_Index[l1] = r1
print(ans)


import bisect
n = int(input())
p = list(map(int, input().split()))
idx = [0] * (n + 1)
for (i, p_i) in enumerate(p):
	idx[p_i] = i
right_idx = list(range(1, n + 1)) + [n, n]
left_idx = list(range(-1, n - 1)) + [-1, -1]
ans = 0
for p in range(1, n + 1):
	x = idx[p]
	r1 = right_idx[x]
	r2 = right_idx[r1]
	l1 = left_idx[x]
	l2 = left_idx[l1]
	ans += p * ((x - l1) * (r2 - r1) + (l1 - l2) * (r1 - x))
	right_idx[l1] = r1
	left_idx[r1] = l1
print(ans)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter
n = int(readline())
ppp = list(map(int, readline().split()))

def BIT_add(i, x):
	while i <= n:
		tree[i] += x
		i += i & -i

def BIT_sum(i):
	s = 0
	while i:
		s += tree[i]
		i -= i & -i
	return s

def BIT_search(x):
	i = 0
	s = 0
	step = 1 << n.bit_length() - 1
	while step:
		if i + step <= n and s + tree[i + step] < x:
			i += step
			s += tree[i]
		step >>= 1
	return i + 1
q = sorted(enumerate(ppp, 1), key=itemgetter(1), reverse=True)
tree = [0] * (n + 1)
ans = 0
for (i, p) in q:
	L = BIT_sum(i)
	BIT_add(i, 1)
	R = n - p - L
	LL = BIT_search(L - 1) if L >= 2 else 0
	LR = BIT_search(L) if L >= 1 else 0
	RL = BIT_search(L + 2) if R >= 1 else n + 1
	RR = BIT_search(L + 3) if R >= 2 else n + 1
	ans += p * ((LR - LL) * (RL - i) + (RR - RL) * (i - LR))
print(ans)


n = int(input())
p = list(map(int, input().split()))
id = [0] * (n + 1)
for (i, p_i) in enumerate(p):
	id[p_i] = i
r = list(range(1, n + 1)) + [n, n]
l = list(range(-1, n - 1)) + [-1, -1]
ans = 0
for p in range(1, n + 1):
	x = id[p]
	r1 = r[x]
	r2 = r[r1]
	l1 = l[x]
	l2 = l[l1]
	ans += p * ((x - l1) * (r2 - r1) + (l1 - l2) * (r1 - x))
	r[l1] = r1
	l[r1] = l1
print(ans)


class Node:

	def __init__(self, key=None):
		self.key = key
		self.balance = 'E'
		self.parent = None
		self.left = None
		self.right = None

class AVL:

	def __init__(self):
		self.root = Node()
		self.root.parent = Node('nil')

	def insert(self, key):
		if self.root.key is None:
			self.root.key = key
			return
		cursor = self.root
		while cursor:
			p = cursor
			if key == cursor.key:
				return
			elif key < cursor.key:
				cursor = cursor.left
			else:
				cursor = cursor.right
		new_node = Node(key)
		new_node.parent = p
		if key < p.key:
			p.left = new_node
		else:
			p.right = new_node
		return self.rebalance(p, new_node, key)

	def rebalance(self, u, v, key):
		while u.key != 'nil':
			if u.key > v.key:
				if u.balance == 'R':
					u.balance = 'E'
					return
				elif u.balance == 'L':
					if v.balance == 'L':
						self.rotate_R(u, v)
						return
					elif v.balance == 'R':
						self.rotate_LR(u, v)
						return
				else:
					u.balance = 'L'
					v = u
					u = u.parent
			elif u.balance == 'L':
				u.balance = 'E'
				return
			elif u.balance == 'R':
				if v.balance == 'R':
					self.rotate_L(u, v)
					return
				elif v.balance == 'L':
					self.rotate_RL(u, v)
					return
			else:
				u.balance = 'R'
				v = u
				u = u.parent

	def replace(self, u, v):
		if u.parent.left == u:
			u.parent.left = v
		else:
			u.parent.right = v
		v.parent = u.parent
		if v.parent.key == 'nil':
			self.root = v

	def rotate_R(self, u, v):
		w = v.right
		self.replace(u, v)
		v.right = u
		u.parent = v
		u.left = w
		if w:
			w.parent = u
		u.balance = 'E'
		v.balance = 'E'

	def rotate_L(self, u, v):
		w = v.left
		self.replace(u, v)
		v.left = u
		u.parent = v
		u.right = w
		if w:
			w.parent = u
		u.balance = 'E'
		v.balance = 'E'

	def rotate_LR(self, u, v):
		w = v.right
		self.replace(u, w)
		if w.left:
			v.right = w.left
			v.right.parent = v
		else:
			v.right = None
		if w.right:
			u.left = w.right
			u.left.parent = u
		else:
			u.left = None
		v.parent = w
		w.left = v
		u.parent = w
		w.right = u
		if w.balance == 'R':
			u.balance = 'E'
			v.balance = 'L'
		elif w.balance == 'L':
			u.balance = 'R'
			v.balance = 'E'
		else:
			u.balance = 'E'
			v.balance = 'E'
		w.balance = 'E'

	def rotate_RL(self, u, v):
		w = v.left
		self.replace(u, w)
		if w.left:
			w.left.parent = u
			u.right = w.left
		else:
			u.right = None
		if w.right:
			w.right.parent = v
			v.left = w.right
		else:
			v.left = None
		u.parent = w
		w.left = u
		v.parent = w
		w.right = v
		if w.balance == 'R':
			u.balance = 'L'
			v.balance = 'E'
		elif w.balance == 'L':
			u.balance = 'E'
			v.balance = 'R'
		else:
			u.balance = 'E'
			v.balance = 'E'
		w.balance = 'E'

	def find(self, key):
		cursor = self.root
		while cursor:
			if cursor.key == key:
				return cursor
			if key < cursor.key:
				cursor = cursor.left
			else:
				cursor = cursor.right
		return None

	def next_greater_key(self, cursor):
		if cursor is None:
			return
		if cursor.right:
			cursor = cursor.right
			while cursor.left:
				cursor = cursor.left
			return cursor
		elif cursor.parent.left == cursor:
			return cursor.parent
		elif cursor.parent.right == cursor:
			while cursor.parent.key != 'nil' and cursor.parent.right == cursor:
				cursor = cursor.parent
			if cursor.parent.key != 'nil':
				return cursor.parent
		else:
			return None

	def next_smaller_key(self, cursor):
		if cursor is None:
			return
		if cursor.left:
			cursor = cursor.left
			while cursor.right:
				cursor = cursor.right
			return cursor
		elif cursor.parent.right == cursor:
			return cursor.parent
		elif cursor.parent.left == cursor:
			while cursor.parent.key != 'nil' and cursor.parent.left == cursor:
				cursor = cursor.parent
			if cursor.parent.key != 'nil':
				return cursor.parent

	def get_smaller_key(self, key):
		cursor = self.find(key)
		l1 = self.next_smaller_key(cursor)
		l2 = self.next_smaller_key(l1)
		if l2 is None:
			l2 = 0
		else:
			l2 = l2.key
		return (l1.key, l2)

	def get_greater_key(self, key):
		cursor = self.find(key)
		r1 = self.next_greater_key(cursor)
		r2 = self.next_greater_key(r1)
		if r2 is None:
			r2 = 0
		else:
			r2 = r2.key
		return (r1.key, r2)

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	P = map(int, input().split())
	idx = [-1] * (N + 1)
	for (i, v) in enumerate(P, 1):
		idx[v] = i
	avl = AVL()
	for i in [0, idx[N], N + 1]:
		avl.insert(i)
	total = 0
	for j in range(N - 1, 0, -1):
		n = idx[j]
		avl.insert(n)
		(l1_idx, l2_idx) = avl.get_smaller_key(n)
		l1 = n - l1_idx
		if l1_idx != 0:
			l2 = l1_idx - l2_idx
		else:
			l2 = 0
		(r1_idx, r2_idx) = avl.get_greater_key(n)
		r1 = r1_idx - n
		if r1_idx != N + 1:
			r2 = r2_idx - r1_idx
		else:
			r2 = 0
		cnt = (l1 * r2 + r1 * l2) * j
		total += cnt
	print(total)

def __starting_point():
	main()
__starting_point()


class BinaryIndexedTree:

	def __init__(self, size):
		self.data = [0] * (size + 1)
		self.msb = 1 << size.bit_length() - 1

	def add(self, i, w):
		i += 1
		while i < len(self.data):
			self.data[i] += w
			i += i & -i

	def get_sum(self, i):
		res = 0
		while i > 0:
			res += self.data[i]
			i -= i & -i
		return res

	def __getitem__(self, i):
		if isinstance(i, slice):
			return self.get_sum(i.stop) if i.start is None else self.get_sum(i.stop) - self.get_sum(i.start)
		else:
			return 0
	__setitem__ = add

	def bisect_left(self, v):
		i = 0
		k = self.msb
		while k > 0:
			i += k
			if i < len(self.data) and self.data[i] < v:
				v -= self.data[i]
			else:
				i -= k
			k >>= 1
		return i

	def bisect_right(self, v):
		i = 0
		k = self.msb
		while k > 0:
			i += k
			if i < len(self.data) and self.data[i] <= v:
				v -= self.data[i]
			else:
				i -= k
			k >>= 1
		return i
	bisect = bisect_right

def naive(P):

	def it():
		for i in range(len(P) - 1):
			for j in range(i + 1, len(P)):
				yield sorted(P[i:j + 1])[-2]
	return sum(it())

def solve(P):

	def it():
		bit = BinaryIndexedTree(len(P))
		for (cnt, (v, i)) in enumerate(sorted(((v, i) for (i, v) in enumerate(P)), reverse=True)):
			bit[i] += 1
			c = bit.get_sum(i)
			low1 = -1 if c <= 0 else bit.bisect_left(c)
			low2 = -1 if c <= 1 else bit.bisect_left(c - 1)
			up1 = len(P) if c > cnt - 1 else bit.bisect_left(c + 2)
			up2 = len(P) if c > cnt - 2 else bit.bisect_left(c + 3)
			yield (v * ((up1 - i) * (low1 - low2) + (i - low1) * (up2 - up1)))
	return sum(it())
N = int(input())
P = list(map(int, input().split()))
print(solve(P))


import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
INF = float('inf')

class BIT:

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

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

	def sum(self, index):
		ret = 0
		while index:
			ret += self.tree[index]
			index -= index & -index
		return ret

	def search(self, value):
		i = 0
		s = 0
		step = 1 << self.size.bit_length() - 1
		while step:
			if i + step <= self.size and s + self.tree[i + step] < value:
				i += step
				s += self.tree[i]
			step //= 2
		return i + 1

def sol():
	N = int(input())
	P = [None] + list(map(int, input().split()))
	ans = 0
	pToIndex = {p: i for (i, p) in enumerate(P[1:], 1)}
	tree = BIT(N)
	for p in range(1, N + 1)[::-1]:
		c = pToIndex[p]
		left = tree.sum(c)
		tree.add(c)
		right = N - p - left
		a = tree.search(left - 1) if left >= 2 else 0
		b = tree.search(left) if left >= 1 else 0
		d = tree.search(left + 2) if right >= 1 else N + 1
		e = tree.search(left + 3) if right >= 2 else N + 1
		cnt = 0
		if b != 0:
			cnt += (b - a) * (d - c)
		if d != 0:
			cnt += (e - d) * (c - b)
		ans += cnt * p
	print(ans)
sol()


import sys
stdin = sys.stdin
ni = lambda : int(ns())
nl = lambda : list(map(int, stdin.readline().split()))
nm = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
n = ni()
p = nl()
q = [0] * (n + 1)
for i in range(n):
	q[p[i]] = i + 1
ans = 0
l = [0] + [i for i in range(n + 1)]
r = [i + 1 for i in range(n + 1)] + [n + 1]
for i in range(1, n + 1):
	v = q[i]
	(l1, r1) = (l[v], r[v])
	(l2, r2) = (l[l1], r[r1])
	ans += i * ((v - l1) * (r2 - r1) + (r1 - v) * (l1 - l2))
	l[r1] = l1
	r[l1] = r1
print(ans)


from bisect import bisect_left, bisect_right, insort_right

class CubeSkipList:

	def __init__(self, values=None, sorted_=False, cube=100, seed=42):
		inf = float('inf')
		self.rand_y = seed
		self.cube = cube
		if values is None:
			self.layer2 = [inf]
			self.layer1 = [[]]
			self.layer0 = [[[]]]
		else:
			self.layer2 = layer2 = []
			self.layer1 = layer1 = []
			self.layer0 = layer0 = []
			if not sorted_:
				values.sort()
			rand_depth = self.rand_depth
			l1 = []
			la0 = []
			l0 = []
			for v in values:
				r = rand_depth()
				if r == 0:
					l0.append(v)
				elif r == 1:
					la0.append(l0)
					l0 = []
					l1.append(v)
				else:
					la0.append(l0)
					layer0.append(la0)
					layer1.append(l1)
					l0 = []
					la0 = []
					l1 = []
					layer2.append(v)
			la0.append(l0)
			layer0.append(la0)
			layer1.append(l1)
			layer2.append(inf)

	def rand_depth(self):
		y = self.rand_y
		y ^= y << 13 & 4294967295
		y ^= y >> 17
		y ^= y << 5 & 4294967295
		self.rand_y = y
		if y % self.cube == 0:
			if y % self.cube ** 2 == 0:
				return 2
			return 1
		return 0

	def add(self, x):
		(layer2, layer1, layer0) = (self.layer2, self.layer1, self.layer0)
		r = self.rand_depth()
		if r == 0:
			idx2 = bisect_right(layer2, x)
			idx1 = bisect_right(layer1[idx2], x)
			insort_right(layer0[idx2][idx1], x)
		elif r == 1:
			idx2 = bisect_right(layer2, x)
			l1 = layer1[idx2]
			idx1 = bisect_right(l1, x)
			l1.insert(idx1, x)
			la0 = layer0[idx2]
			l0 = la0[idx1]
			idx0 = bisect_right(l0, x)
			la0.insert(idx1 + 1, l0[idx0:])
			del l0[idx0:]
		else:
			idx2 = bisect_right(layer2, x)
			layer2.insert(idx2, x)
			l1 = layer1[idx2]
			idx1 = bisect_right(l1, x)
			la0 = layer0[idx2]
			l0 = la0[idx1]
			idx0 = bisect_right(l0, x)
			la0.insert(idx1 + 1, l0[idx0:])
			del l0[idx0:]
			layer0.insert(idx2 + 1, la0[idx1 + 1:])
			del la0[idx1 + 1:]
			layer1.insert(idx2 + 1, l1[idx1:])
			del l1[idx1:]

	def remove(self, x):
		raise NotImplementedError
		(layer1, layer0) = (self.layer1, self.layer0)
		idx1 = bisect_left(layer1, x)
		if layer1[idx1] == x:
			del layer1[idx1]
			layer0[idx1] += layer0[idx1 + 1]
			del layer0[idx1 + 1]
		else:
			layer0_idx1 = layer0[idx1]
			del layer0_idx1[bisect_left(layer0_idx1, x)]

	def bisect_left(self, x):
		raise NotImplementedError
		(layer1, layer0) = (self.layer1, self.layer0)
		idx1 = bisect_left(layer1, x)
		res = layer1[idx1]
		if res == x:
			return res
		layer0_idx1 = layer0[idx1]
		if layer0_idx1:
			idx0 = bisect_left(layer0_idx1, x)
			if idx0 == len(layer0_idx1):
				return res
			else:
				return layer0_idx1[idx0]
		else:
			return res

	def search_higher(self, x):
		(layer2, layer1, layer0) = (self.layer2, self.layer1, self.layer0)
		idx2 = bisect_right(layer2, x)
		l1 = layer1[idx2]
		idx1 = bisect_right(l1, x)
		la0 = layer0[idx2]
		l0 = la0[idx1]
		idx0 = bisect_right(l0, x)
		if idx0 == len(l0):
			if idx1 == len(l1):
				return layer2[idx2]
			return l1[idx1]
		return l0[idx0]

	def search_lower(self, x):
		(layer2, layer1, layer0) = (self.layer2, self.layer1, self.layer0)
		idx2 = bisect_left(layer2, x)
		l1 = layer1[idx2]
		idx1 = bisect_left(l1, x)
		la0 = layer0[idx2]
		l0 = la0[idx1]
		idx0 = bisect_left(l0, x)
		if idx0 == 0:
			if idx1 == 0:
				return layer2[idx2 - 1]
			return l1[idx1 - 1]
		return l0[idx0 - 1]

	def pop(self, idx):
		raise NotImplementedError
		(layer1, layer0) = (self.layer1, self.layer0)
		s = -1
		for (i, l0) in enumerate(layer0):
			s += len(l0) + 1
			if s >= idx:
				break
		if s == idx:
			layer0[i] += layer0[i + 1]
			del layer0[i + 1]
			return layer1.pop(i)
		else:
			return layer0[i].pop(idx - s)

	def print(self):
		print(self.layer2)
		print(self.layer1)
		print(self.layer0)

def main():
	n = int(input())
	p = list(map(int, input().split()))
	idx = [0] * n
	for i in range(0, n):
		idx[i] = i
	idx.sort(key=lambda i: -p[i])
	ssl = CubeSkipList()
	ssl.add(-1)
	ssl.add(n)
	ans = 0
	for i in idx:
		nex = ssl.search_higher(i)
		nexnex = ssl.search_higher(nex)
		pre = ssl.search_lower(i)
		prepre = ssl.search_lower(pre)
		if prepre != float('inf'):
			ans += p[i] * (pre - prepre) * (nex - i)
		if nexnex != float('inf'):
			ans += p[i] * (i - pre) * (nexnex - nex)
		ssl.add(i)
	print(ans)
main()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
(n, *p) = map(int, read().split())
ans = 0
l = list(range(n))
r = list(range(n))
memo = [-1] * (n + 1)
for (i, pp) in enumerate(p):
	memo[pp] = i
for (i, idx) in enumerate(memo[1:], 1):
	l1 = idx - 1
	r1 = idx + 1
	while l1 >= 0 and l1 != l[l1]:
		l1 = l[l1]
	while r1 < n and r1 != r[r1]:
		r1 = r[r1]
	l[idx] = l1
	r[idx] = r1
	if l1 != -1:
		l2 = l1 - 1
		while l2 >= 0 and l2 != l[l2]:
			l2 = l[l2]
		ans += (l1 - l2) * (r1 - idx) * i
	if r1 != n:
		r2 = r1 + 1
		while r2 < n and r2 != r[r2]:
			r2 = r[r2]
		ans += (r2 - r1) * (idx - l1) * i
print(ans)


from heapq import heappush, heappop
N = int(input())
P = [int(i) for i in input().split()]
dpl = [[] for _ in range(N)]
dpr = [[] for _ in range(N)]
q = []
for i in range(N - 1, -1, -1):
	L = []
	while len(q) > 0 and q[0][0] < P[i]:
		(v, j) = heappop(q)
		if len(dpl[j]) == 0:
			L.append([v, j])
		dpl[j].append(i)
	for (v, j) in L:
		heappush(q, [v, j])
	heappush(q, [P[i], i])
q = []
for i in range(N):
	L = []
	while len(q) > 0 and q[0][0] < P[i]:
		(v, j) = heappop(q)
		if len(dpr[j]) == 0:
			L.append([v, j])
		dpr[j].append(i)
	for (v, j) in L:
		heappush(q, [v, j])
	heappush(q, [P[i], i])
for i in range(N):
	for _ in range(2 - len(dpl[i])):
		dpl[i].append(-1)
	for _ in range(2 - len(dpr[i])):
		dpr[i].append(N)
	dpl[i].sort()
	dpr[i].sort()
ret = 0
for i in range(N):
	ret += (dpl[i][1] - dpl[i][0]) * (dpr[i][0] - i) * P[i]
	ret += (i - dpl[i][1]) * (dpr[i][1] - dpr[i][0]) * P[i]
print(ret)


import sys
input = sys.stdin.readline
N = int(input())
P = list(map(int, input().split()))

class SegmentTree:

	def __init__(self, data, op, default):
		N = len(data)
		self.N = N
		self.op = op
		self.default = default
		self.l = 2 ** (N - 1).bit_length()
		self.data = [default] * self.l + data + [default] * (self.l - N)
		for i in range(self.l - 1, 0, -1):
			self.data[i] = op(self.data[2 * i], self.data[2 * i + 1])

	def get_data(self):
		return self.data[self.l:self.l + self.N]

	def set(self, i, val):
		i += self.l
		self.data[i] = val
		i = i // 2
		while i > 0:
			self.data[i] = self.op(self.data[2 * i], self.data[2 * i + 1])
			i = i // 2

	def get(self, i, j):
		i += self.l
		j += self.l
		s = self.default
		while j - i > 0:
			if i & 1:
				s = self.op(s, self.data[i])
				i += 1
			if j & 1:
				s = self.op(s, self.data[j - 1])
				j -= 1
			i = i // 2
			j = j // 2
		return s
P2 = [[[p, i], [0, 0]] for (i, p) in enumerate(P)]
max2 = lambda x, y: sorted(x + y, reverse=True)[:2]
seg = SegmentTree(P2, max2, [[0, 0], [0, 0]])
cand = [[0, N]]
ans = 0
visited = set([])
while cand:
	temp = []
	for (l, r) in cand:
		if r - l < 2:
			continue
		if (l, r) in visited:
			continue
		visited.add((l, r))
		((m1, i1), (m2, i2)) = seg.get(l, r)
		(i1, i2) = (i1, i2) if i1 < i2 else (i2, i1)
		ans += m2 * (i1 - l + 1) * (r - i2)
		temp.append([l, i2])
		temp.append([i1 + 1, r])
	cand = temp
print(ans)


from bisect import bisect_left
import array
n = int(input())
p = []
for (i, x) in enumerate(map(int, input().split())):
	p.append([x, i])
p.sort(reverse=True)
s = array.array('i', [-1, -1, p[0][1], n, n])
ans = 0
i = 2
for (a, x) in p[1:]:
	t = bisect_left(s, x)
	ans += a * ((x - s[t - 1]) * (s[t + 1] - s[t]) + (s[t] - x) * (s[t - 1] - s[t - 2]))
	s.insert(t, x)
	i += 1
print(ans)


from bisect import bisect_left, bisect_right

class OrderedSet:

	def __init__(self, a):
		self.c = {}
		self.a_sort = sorted(list(set(a)))
		for (i, a) in enumerate(self.a_sort):
			self.c[a] = i + 1
		self.r = {v: k for (k, v) in self.c.items()}
		self.size = len(self.c)
		self.tree = [0] * (self.size + 1)
		self.num = [0] * self.size
		self.all_count = 0

	def _sum(self, index):
		s = 0
		while index:
			s += self.tree[index]
			index -= index & -index
		return s

	def insert(self, x, k=1):
		index = self.c[x]
		self.num[index - 1] += k
		while index <= self.size:
			self.tree[index] += k
			index += index & -index
		self.all_count += k

	def erase(self, x, k=1):
		self.insert(x, k=-k)

	def count(self, x):
		return self.num[self.c[x] - 1]

	def get_kth_bottom(self, k):
		if k <= 0:
			return None
		elif self.all_count < k:
			return None
		else:
			i = 0
			s = 0
			step = 1 << self.size.bit_length() - 1
			while step:
				if i + step <= self.size and s + self.tree[i + step] < k:
					i += step
					s += self.tree[i]
				step >>= 1
			return self.r[i + 1]

	def get_kth_top(self, k):
		return self.get_kth_bottom(self.all_count - k + 1)

	def lower_bound(self, x):
		p = bisect_left(self.a_sort, x)
		if p == 0:
			k = 1
		else:
			k = self._sum(p) + 1
		return self.get_kth_bottom(k)

	def upper_bound(self, x):
		p = bisect_right(self.a_sort, x)
		if p == 0:
			return None
		else:
			k = self._sum(p)
			return self.get_kth_bottom(k)

def resolve():
	N = int(input())
	A = list(map(int, input().split()))
	P = [0] * (N + 1)
	for i in range(N):
		P[A[i]] = i + 1
	OS = OrderedSet(P)
	ans = 0
	for i in range(N, 0, -1):
		p = P[i]
		c = OS.lower_bound(p)
		d = None if c is None else OS.lower_bound(c + 1)
		b = OS.upper_bound(p)
		a = None if b is None else OS.upper_bound(b - 1)
		a = a if a is not None else 0
		d = d if d is not None else N + 1
		if b is None:
			if c is not None:
				ans += i * p * (d - c)
		elif c is None:
			ans += i * (b - a) * (N - p + 1)
		else:
			ans += i * ((b - a) * (c - p) + (p - b) * (d - c))
		OS.insert(p)
	print(ans)
resolve()


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 13

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class BIT:

	def __init__(self, size):
		self.bit = [0] * size
		self.size = size
		self.total = 0

	def add(self, i, w):
		x = i + 1
		self.total += w
		while x <= self.size:
			self.bit[x - 1] += w
			x += x & -x
		return

	def sum(self, i):
		res = 0
		x = i + 1
		while x:
			res += self.bit[x - 1]
			x -= x & -x
		return res

	def interval_sum(self, i, j):
		return self.sum(j - 1) - self.sum(i - 1)

	def search(self, k):
		if k > self.total or k <= 0:
			return -1
		step = 1 << self.size.bit_length() - 1
		now_index = 0
		ret = 0
		while step:
			if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
				ret += self.bit[now_index + step - 1]
				now_index += step
			step >>= 1
		return now_index
n = I()
P = LI()
val_idx = {P[j]: j + 1 for j in range(n)}
bit = BIT(n + 2)
bit.add(n + 1, 1)
bit.add(0, 1)
ans = 0
for k in range(n, 0, -1):
	idx = val_idx[k]
	m = bit.sum(idx)
	l1 = bit.search(m - 1)
	l2 = bit.search(m)
	r1 = bit.search(m + 1)
	r2 = bit.search(m + 2)
	if l1 >= 0:
		ans += (l2 - l1) * (r1 - idx) * k
	if r2 >= 0:
		ans += (idx - l2) * (r2 - r1) * k
	bit.add(idx, 1)
print(ans)


class SegTree:

	def __init__(self, N, e=0, operator_func=lambda x, y: x + y):
		self.e = e
		self.N = N
		bitlen = N.bit_length()
		self.size = 2 ** (bitlen if N & N - 1 else bitlen - 1)
		self.node = [self.e] * (2 * self.size)
		self.op = operator_func

	def set_list(self, l):
		for (i, j) in enumerate(l):
			self.node[i + self.size - 1] = j
		for i in range(self.size - 1)[::-1]:
			self.node[i] = self.op(self.node[2 * i + 1], self.node[2 * i + 2])

	def update(self, k, x):
		k += self.size - 1
		self.node[k] = x
		while k >= 0:
			k = (k - 1) // 2
			self.node[k] = self.op(self.node[2 * k + 1], self.node[2 * k + 2])

	def get(self, l, r):
		x = self.e
		l += self.size
		r += self.size
		(a, b) = ([], [])
		while l < r:
			if l & 1:
				a += [l - 1]
				l += 1
			if r & 1:
				r -= 1
				b += [r - 1]
			l >>= 1
			r >>= 1
		for i in a + b[::-1]:
			x = self.op(x, self.node[i])
		return x

	def bisect_left(self, x):
		if x > self.node[0]:
			return self.N
		(p, ans) = (0, 0)
		node_size = 2 * self.size - 1
		x -= 1
		while p < node_size:
			ans = p - (self.size - 1)
			(p1, p2) = (2 * p + 1, 2 * p + 2)
			if p1 < node_size and self.node[p1] <= x:
				x -= self.node[p1]
				p = p2
			else:
				p = p1
		return ans + 1
N = int(input())
l = [(j, i) for (i, j) in enumerate(map(int, input().split()))]
l.sort(key=lambda x: -x[0])
tree = SegTree(N)
ans = 0
for (n, (value, idx)) in enumerate(l, start=1):
	v = tree.get(0, idx + 1)
	a = tree.bisect_left(v - 1) if v > 1 else 0
	b = tree.bisect_left(v - 0) if v else 0
	c = tree.bisect_left(v + 1) if n - v > 1 else N + 1
	d = tree.bisect_left(v + 2) if n - v > 2 else N + 1
	tree.update(idx, 1)
	idx += 1
	ans += ((b - a) * (c - idx) + (d - c) * (idx - b)) * value
print(ans)


class SegTree:

	def __init__(self, init_val, n, ide_ele, seg_func):
		self.segfunc = seg_func
		self.num = 2 ** (n - 1).bit_length()
		self.ide_ele = ide_ele
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k + 1:
			k = (k - 1) // 2
			self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = self.segfunc(res, self.seg[p])
			if q & 1 == 1:
				res = self.segfunc(res, self.seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = self.segfunc(res, self.seg[p])
		else:
			res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
		return res
n = int(input())
xs = list(map(int, input().split()))
x2i = {}
for (i, x) in enumerate(xs):
	x2i[x] = i
ss1 = SegTree([n] * n, n, n, min)
ss2 = SegTree([-1] * n, n, -1, max)
r = 0
for x in range(n):
	x = n - x
	rmi2 = ss1.query(x2i[x] + 1, n)
	if rmi2 != n:
		ss1.update(rmi2, n)
	rmi = ss1.query(x2i[x] + 1, n)
	if rmi2 != n:
		ss1.update(rmi2, rmi2)
	lmi = ss2.query(0, x2i[x])
	if lmi != -1:
		ss2.update(lmi, -1)
	lmi2 = ss2.query(0, x2i[x])
	if lmi != -1:
		ss2.update(lmi, lmi)
	(a, b, c, d) = (x2i[x] - lmi, lmi - lmi2, rmi - rmi2, rmi2 - x2i[x])
	r += (a * c + b * d) * x
	ss1.update(x2i[x], x2i[x])
	ss2.update(x2i[x], x2i[x])
print(r)


import sys
sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline

class BinaryIndexedTree:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)

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

	def sum(self, i):
		res = 0
		while i:
			res += self.data[i]
			i -= i & -i
		return res

	def bisect_left(self, w):
		if w <= 0:
			return 0
		i = 0
		k = 1 << self.n.bit_length() - 1
		while 0 < k:
			if i + k <= self.n and self.data[i + k] < w:
				w -= self.data[i + k]
				i += k
			k >>= 1
		return i + 1

def solve():
	N = int(rl())
	P = list(map(int, rl().split()))
	p_to_idx = [0] * (N + 1)
	for (i, x) in enumerate(P):
		p_to_idx[x] = i + 1
	bit = BinaryIndexedTree(N)
	ans = 0
	for pi in range(N, 0, -1):
		idx = p_to_idx[pi]
		left = bit.sum(idx)
		bit.add(idx, 1)
		right = N - pi - left
		l0 = bit.bisect_left(left - 1) if 2 <= left else 0
		l1 = bit.bisect_left(left) if 1 <= left else 0
		r0 = bit.bisect_left(left + 2) if 1 <= right else N + 1
		r1 = bit.bisect_left(left + 3) if 2 <= right else N + 1
		cnt = 0
		if l1 != 0:
			cnt += (l1 - l0) * (r0 - idx)
		if r0 != 0:
			cnt += (r1 - r0) * (idx - l1)
		ans += pi * cnt
	print(ans)
solve()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(N, *P) = map(int, read().split())
INF = N + 100
P = [INF, INF] + P + [INF, INF]
x_to_i = [0] * (INF + 1)
for (i, x) in enumerate(P):
	x_to_i[x] = i
left = list(range(N + 4))
right = list(range(N + 4))
filled = [False] * (N + 4)
answer = 0
for (x, i) in enumerate(x_to_i[1:N + 1], 1):
	filled[i] = True
	L = left[i - 1] if filled[i - 1] else i
	R = right[i + 1] if filled[i + 1] else i
	right[L] = R
	left[R] = L
	c = i
	b = L - 1
	d = R + 1
	a = left[L - 2] - 1 if filled[L - 2] else L - 2
	e = right[R + 2] + 1 if filled[R + 2] else R + 2
	coef = 0
	if b >= 2:
		coef += (b - a) * (d - c)
	if d <= N + 1:
		coef += (e - d) * (c - b)
	answer += x * coef
print(answer)


def resolve():
	N = int(input())
	A = list(map(int, input().split()))
	P = [0] * (N + 1)
	for (i, a) in enumerate(A):
		P[a] = i
	l_idx = list(range(-1, N - 1)) + [-1, -1]
	r_idx = list(range(1, N + 1)) + [N, N]
	ans = 0
	for p in range(1, N + 1):
		x = P[p]
		l1 = l_idx[x]
		l2 = l_idx[l1]
		r1 = r_idx[x]
		r2 = r_idx[r1]
		cmb = (x - l1) * (r2 - r1) + (l1 - l2) * (r1 - x)
		ans += p * cmb
		l_idx[r1] = l1
		r_idx[l1] = r1
	print(ans)
resolve()


INF = 10 ** 6

class SegTree:

	def __init__(self, A):
		n_ = len(A)
		self.n = 1
		while self.n < n_:
			self.n *= 2
		self.tree = [INF for _ in range(2 * self.n - 1)]
		for (k, a) in enumerate(A):
			self.update(k, a)

	def update(self, k, a):
		k += self.n - 1
		self.tree[k] = a
		while k > 0:
			k = (k - 1) // 2
			self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])

	def query(self, l, r):
		l += self.n - 1
		r += self.n - 2
		res = INF
		while r - l > 1:
			if l & 1 == 0:
				res = min(res, self.tree[l])
			if r & 1 == 1:
				res = min(res, self.tree[r])
				r -= 1
			l = l // 2
			r = (r - 1) // 2
		if l == r:
			res = min(res, self.tree[l])
		else:
			res = min(min(res, self.tree[l]), self.tree[r])
		return res
n = int(input())
p = list(map(int, input().split()))
pii = []
for (i, pi) in enumerate(p):
	pii.append([pi, i])
pii.sort(reverse=True)
st_r = SegTree([n] * (n + 1))
st_l = SegTree([1] * (n + 1))
ans = 0
for (pi, i) in pii:
	if pi < n:
		l = -st_l.query(0, i)
		r = st_r.query(i + 1, n)
		if l != -1:
			l2 = l - 1
			if l > 0:
				l2 = -st_l.query(0, l)
			ans += (l - l2) * (r - i) * pi
		if r != n:
			r2 = r + 1
			if r < n - 1:
				r2 = st_r.query(r + 1, n)
			ans += (i - l) * (r2 - r) * pi
	st_r.update(i, i)
	st_l.update(i, -i)
print(ans)


def main():
	import sys
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 7)
	from collections import Counter, deque
	from itertools import combinations, permutations, accumulate, groupby, product
	from bisect import bisect_left, bisect_right
	from heapq import heapify, heappop, heappush
	import math
	n = int(input())
	p = list(map(int, input().split()))
	f = [0] * (n + 1)
	for i in range(n):
		f[p[i]] = i + 1
	l = [0] + [i for i in range(n + 1)]
	r = [i + 1 for i in range(n + 1)] + [n + 1]
	res = 0
	for i in range(1, n + 1):
		x = f[i]
		(l1, r1) = (l[x], r[x])
		(l2, r2) = (l[l1], r[r1])
		res += ((l1 - l2) * (r1 - x) + (x - l1) * (r2 - r1)) * i
		(l[r1], r[l1]) = (l1, r1)
	print(res)
main()


class BIT:

	def __init__(self, size):
		self.size = size
		self.data = [0] * (size + 1)

	def add(self, index, value=1):
		while index <= self.size:
			self.data[index] += value
			index += index & -index

	def sum(self, index):
		ret = 0
		while index:
			ret += self.data[index]
			index -= index & -index
		return ret

	def search(self, val):
		i = 0
		s = 0
		step = 1 << self.size.bit_length() - 1
		while step:
			if i + step <= self.size and s + self.data[i + step] < val:
				i += step
				s += self.data[i]
			step //= 2
		return i + 1

def sol():
	N = int(input())
	P = [None] + list(map(int, input().split()))
	pToI = {p: i for (i, p) in enumerate(P[1:], 1)}
	tree = BIT(N)
	ans = 0
	for p in range(1, N + 1)[::-1]:
		i = pToI[p]
		left = tree.sum(i)
		tree.add(i)
		right = N - p - left
		L1 = tree.search(left - 1) if left >= 2 else 0
		L2 = tree.search(left) if left >= 1 else 0
		R1 = tree.search(left + 2) if right >= 1 else N + 1
		R2 = tree.search(left + 3) if right >= 2 else N + 1
		cnt = 0
		if L2 != 0:
			cnt += (L2 - L1) * (R1 - i)
		if R1 != 0:
			cnt += (R2 - R1) * (i - L2)
		ans += cnt * p
	print(ans)
sol()


class SegTree:

	def __init__(self, N, function, basement):
		self.n = N
		self.K = (self.n - 1).bit_length()
		self.f = function
		self.b = basement
		self.seg = [basement] * (2 ** (self.K + 1) + 1)
		X = 2 ** self.K

	def update(self, k, value):
		X = 2 ** self.K
		k += X
		self.seg[k] = value
		while k:
			k = k >> 1
			self.seg[k] = self.f(self.seg[k << 1], self.seg[k << 1 | 1])

	def query(self, L, R):
		num = 2 ** self.K
		L += num
		R += num
		vL = self.b
		vR = self.b
		while L < R:
			if L & 1:
				vL = self.f(vL, self.seg[L])
				L += 1
			if R & 1:
				R -= 1
				vR = self.f(self.seg[R], vR)
			L >>= 1
			R >>= 1
		return self.f(vL, vR)

	def find_max_index(self, L, R, X):
		return self.fMi(L, R, X, 1, 0, 2 ** self.K)

	def find_min_index(self, L, R, X):
		return self.fmi(L, R, X, 1, 0, 2 ** self.K)

	def fMi(self, a, b, x, k, l, r):
		if self.seg[k] < x or r <= a or b <= l:
			return -1
		elif k >= 2 ** self.K:
			return k - 2 ** self.K
		else:
			vr = self.fMi(a, b, x, k << 1 | 1, (l + r) // 2, r)
			if vr != -1:
				return vr
			return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

	def fmi(self, a, b, x, k, l, r):
		if self.seg[k] < x or r <= a or b <= l:
			return -1
		elif k >= 2 ** self.K:
			return k - 2 ** self.K
		else:
			vl = self.fmi(a, b, x, k << 1, l, (l + r) // 2)
			if vl != -1:
				return vl
			return self.fmi(a, b, x, k << 1 | 1, (l + r) // 2, r)
xx = int(input())
P = list(map(int, input().split()))
P = [10 ** 18, 10 ** 18] + P + [10 ** 18, 10 ** 18]
Q = []
for (i, v) in enumerate(P):
	Q.append((v, i))
Q.sort(reverse=True)
N = len(Q)
A = SegTree(N, max, 0)
ans = 0
for (value, index) in Q:
	A.update(index, value)
	if value < 10 ** 18:
		l2 = A.find_max_index(0, index, value)
		l1 = A.find_max_index(0, l2, value)
		r1 = A.find_min_index(index + 1, N, value)
		r2 = A.find_min_index(r1 + 1, N, value)
		if 1 < l2:
			ans += value * ((l2 - l1) * (r1 - index))
		if r1 < N - 2:
			ans += value * ((r2 - r1) * (index - l2))
print(ans)


import sys
from heapq import heappush, heappop
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)
		self.step = pow(2, n.bit_length() - 1)

	def add(self, i, x=1):
		i += 1
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get_sum(self, i):
		i += 1
		x = 0
		while i > 0:
			x += self.data[i]
			i -= i & -i
		return x

	def get_sum_range(self, l, r):
		return self.get_sum(r - 1) - self.get_sum(l - 1)

	def lower_bound(self, x):
		if x <= 0:
			return 0
		i = 0
		k = self.step
		while k:
			if i + k <= self.n and self.data[i + k] < x:
				x -= self.data[i + k]
				i += k
			k >>= 1
		return i

def main():
	(N, *P) = map(int, read().split())
	index = [0] * (N + 1)
	for (i, p) in enumerate(P):
		index[p] = i
	bit = BIT(N)
	ans = 0
	for n in range(N, 0, -1):
		i = index[n]
		bit.add(i)
		x = bit.get_sum(i)
		left1 = left2 = -1
		right1 = right2 = N
		if x - 2 > 0:
			left2 = bit.lower_bound(x - 2)
		if x - 1 > 0:
			left1 = bit.lower_bound(x - 1)
		if x + 1 <= N - n + 1:
			right1 = bit.lower_bound(x + 1)
		if x + 2 <= N - n + 1:
			right2 = bit.lower_bound(x + 2)
		ans += ((left1 - left2) * (right1 - i) + (right2 - right1) * (i - left1)) * n
	print(ans)
	return
main()


n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))
left = {i: i - 1 for i in range(n)}
right = {i: i + 1 for i in range(n)}
left[-1] = -1
right[n] = n
ret = 0
for (p, i) in pi:
	ret += p * (left[i] - left[left[i]]) * (right[i] - i)
	ret += p * (i - left[i]) * (right[right[i]] - right[i])
	(l, r) = (left[i], right[i])
	right[l] = r
	left[r] = l
print(ret)


def getN():
	return int(input())

def getNM():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def getArray(intn):
	return [int(input()) for i in range(intn)]

def input():
	return sys.stdin.readline().rstrip()

def rand_N(ran1, ran2):
	return random.randint(ran1, ran2)

def rand_List(ran1, ran2, rantime):
	return [random.randint(ran1, ran2) for i in range(rantime)]

def rand_ints_nodup(ran1, ran2, rantime):
	ns = []
	while len(ns) < rantime:
		n = random.randint(ran1, ran2)
		if not n in ns:
			ns.append(n)
	return sorted(ns)

def rand_query(ran1, ran2, rantime):
	r_query = []
	while len(r_query) < rantime:
		n_q = rand_ints_nodup(ran1, ran2, 2)
		if not n_q in r_query:
			r_query.append(n_q)
	return sorted(r_query)
from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right
import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

class BIT:

	def __init__(self, N):
		self.N = N
		self.bit = [0] * (N + 1)
		self.b = 1 << N.bit_length() - 1

	def add(self, a, w):
		x = a
		while x <= self.N:
			self.bit[x] += w
			x += x & -x

	def get(self, a):
		(ret, x) = (0, a - 1)
		while x > 0:
			ret += self.bit[x]
			x -= x & -x
		return ret

	def cum(self, l, r):
		return self.get(r) - self.get(l)

	def lowerbound(self, w):
		if w <= 0:
			return 0
		x = 0
		k = self.b
		while k > 0:
			if x + k <= self.N and self.bit[x + k] < w:
				w -= self.bit[x + k]
				x += k
			k //= 2
		return x + 1
N = getN()
P = getList()
dic = {}
bit = BIT(N)
for i in range(N):
	dic[P[i]] = i + 1
dic[0] = 0
dic[N + 1] = N + 1
ans = 0
for i in range(N, 0, -1):
	bit.add(dic[i], 1)
	c = bit.get(dic[i] + 1)
	(l1, l2) = (bit.lowerbound(c - 1), bit.lowerbound(c - 2))
	(r1, r2) = (bit.lowerbound(c + 1), bit.lowerbound(c + 2))
	S = (l1 - l2) * (r1 - dic[i]) + (r2 - r1) * (dic[i] - l1)
	ans += S * i
print(ans)


N = int(input())
P = list(map(int, input().split()))
R = list(range(N))
L = list(range(N))
I = [-1] * (N + 1)
for (i, p) in enumerate(P):
	I[p] = i
ans = 0
for (n, idx) in enumerate(I[1:], 1):
	l = idx - 1
	while l >= 0 and l != L[l]:
		l = L[l]
	r = idx + 1
	while r < N and r != R[r]:
		r = R[r]
	L[idx] = l
	R[idx] = r
	if l != -1:
		l2 = l - 1
		while l2 >= 0 and l2 != L[l2]:
			l2 = L[l2]
		ans += n * (l - l2) * (r - idx)
	if r != N:
		r2 = r + 1
		while r2 < N and r2 != R[r2]:
			r2 = R[r2]
		ans += n * (idx - l) * (r2 - r)
print(ans)


class Node:

	def __init__(self, key=None):
		self.key = key
		self.height = 1
		self.parent = None
		self.left = None
		self.right = None

def get_height(t):
	return 0 if t is None else t.height

def get_balance(t):
	return get_height(t.left) - get_height(t.right)

def update_height(t):
	left_height = get_height(t.left)
	right_height = get_height(t.right)
	if left_height >= right_height:
		t.height = left_height + 1
	else:
		t.height = right_height + 1

class AVL:

	def __init__(self):
		self.root = Node()

	def insert(self, key):
		if self.root.key is None:
			self.root.key = key
			return
		cursor = self.root
		while cursor:
			p = cursor
			if key == cursor.key:
				return
			elif key < cursor.key:
				cursor = cursor.left
			else:
				cursor = cursor.right
		new_node = Node(key)
		new_node.parent = p
		if key < p.key:
			p.left = new_node
		else:
			p.right = new_node
		cursor = p
		while cursor:
			balance = get_balance(cursor)
			if balance == 0:
				break
			elif balance == 2:
				if key < cursor.left.key:
					self.rotate_r(cursor)
				else:
					self.rotate_lr(cursor)
				break
			elif balance == -2:
				if key > cursor.right.key:
					self.rotate_l(cursor)
				else:
					self.rotate_rl(cursor)
				break
			else:
				update_height(cursor)
				cursor = cursor.parent

	def rotate_r(self, n):
		p = n.parent
		c = n.left
		gc = n.left.right
		if gc is not None:
			n.left = gc
			gc.parent = n
		else:
			n.left = None
		c.right = n
		n.parent = c
		if p is not None:
			if p.right == n:
				p.right = c
			else:
				p.left = c
			c.parent = p
		else:
			self.root = c
			self.root.parent = None
		update_height(n)
		update_height(c)

	def rotate_l(self, n):
		p = n.parent
		c = n.right
		gc = n.right.left
		if gc is not None:
			n.right = gc
			gc.parent = n
		else:
			n.right = None
		c.left = n
		n.parent = c
		if p is not None:
			if p.left == n:
				p.left = c
			else:
				p.right = c
			c.parent = p
		else:
			self.root = c
			self.root.parent = None
		update_height(n)
		update_height(c)

	def rotate_rl(self, n):
		p = n.parent
		c = n.right
		gc = n.right.left
		if gc.left and gc.right:
			n.right = gc.left
			c.left = gc.right
			gc.left.parent = n
			gc.right.parent = c
		elif gc.left:
			n.right = gc.left
			gc.left.parent = n
			c.left = None
		elif gc.right:
			c.left = gc.right
			gc.right.parent = c
			n.right = None
		else:
			n.right = None
			c.left = None
		gc.left = n
		gc.right = c
		n.parent = gc
		c.parent = gc
		if p is not None:
			if p.left == n:
				p.left = gc
			else:
				p.right = gc
			gc.parent = p
		else:
			self.root = gc
			self.root.parent = None
		update_height(n)
		update_height(c)
		update_height(gc)

	def rotate_lr(self, n):
		p = n.parent
		c = n.left
		gc = n.left.right
		if gc.left and gc.right:
			c.right = gc.left
			n.left = gc.right
			gc.left.parent = c
			gc.right.parent = n
		elif gc.left:
			c.right = gc.left
			gc.left.parent = c
			n.left = None
		elif gc.right:
			n.left = gc.right
			gc.right.parent = n
			c.right = None
		else:
			n.left = None
			c.right = None
		gc.left = c
		gc.right = n
		c.parent = gc
		n.parent = gc
		if p is not None:
			if p.left == n:
				p.left = gc
			else:
				p.right = gc
			gc.parent = p
		else:
			self.root = gc
			self.root.parent = None
		update_height(n)
		update_height(c)
		update_height(gc)

	def find(self, key):
		cursor = self.root
		while cursor:
			if cursor.key == key:
				return cursor
			if key < cursor.key:
				cursor = cursor.left
			else:
				cursor = cursor.right
		return None

	def next_greater_key(self, cursor):
		if cursor is None:
			return None
		if cursor.right:
			cursor = cursor.right
			while cursor.left:
				cursor = cursor.left
			return cursor
		elif cursor.parent.left == cursor:
			return cursor.parent
		elif cursor.parent.right == cursor:
			while cursor.parent and cursor.parent.right == cursor:
				cursor = cursor.parent
			if cursor.parent:
				return cursor.parent
		else:
			return None

	def next_smaller_key(self, cursor):
		if cursor is None:
			return None
		if cursor.left:
			cursor = cursor.left
			while cursor.right:
				cursor = cursor.right
			return cursor
		elif cursor.parent.right == cursor:
			return cursor.parent
		elif cursor.parent.left == cursor:
			while cursor.parent and cursor.parent.left == cursor:
				cursor = cursor.parent
			if cursor.parent:
				return cursor.parent
		else:
			return None

	def get_smaller_key(self, key):
		cursor = self.find(key)
		l1 = self.next_smaller_key(cursor)
		l2 = self.next_smaller_key(l1)
		if l2 is None:
			l2 = 0
		else:
			l2 = l2.key
		return (l1.key, l2)

	def get_greater_key(self, key):
		cursor = self.find(key)
		r1 = self.next_greater_key(cursor)
		r2 = self.next_greater_key(r1)
		if r2 is None:
			r2 = 0
		else:
			r2 = r2.key
		return (r1.key, r2)

def main():
	N = int(input())
	P = map(int, input().split())
	idx = [-1] * (N + 1)
	for (i, v) in enumerate(P, 1):
		idx[v] = i
	avl = AVL()
	for i in [0, idx[N], N + 1]:
		avl.insert(i)
	total = 0
	for j in range(N - 1, 0, -1):
		n = idx[j]
		avl.insert(n)
		(l1_idx, l2_idx) = avl.get_smaller_key(n)
		l1 = n - l1_idx
		if l1_idx != 0:
			l2 = l1_idx - l2_idx
		else:
			l2 = 0
		(r1_idx, r2_idx) = avl.get_greater_key(n)
		r1 = r1_idx - n
		if r1_idx != N + 1:
			r2 = r2_idx - r1_idx
		else:
			r2 = 0
		cnt = (l1 * r2 + r1 * l2) * j
		total += cnt
	print(total)

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.buffer.readline

def main():
	N = int(input())
	p = list(map(int, input().split()))
	nl = [0] * N
	for (i, num) in enumerate(p):
		nl[num - 1] = i + 1
	nl.reverse()

	class BinaryIndexedTree:

		def __init__(self, size, default):
			self.size = size
			self.default = default
			self.BIT = [default] * (self.size + 1)

		def BIT_segfunc(self, x, y):
			return x + y

		def BIT_query(self, idx):
			ret = self.default
			while idx > 0:
				ret = self.BIT_segfunc(ret, self.BIT[idx])
				idx -= idx & -idx
			return ret

		def BIT_update(self, idx, x):
			while idx <= self.size:
				self.BIT[idx] = self.BIT_segfunc(self.BIT[idx], x)
				idx += idx & -idx
			return

		def BIT_range(self, x, y):
			return self.BIT_query(y) - self.BIT_query(x)

		def BIT_print(self):
			print(self.BIT)

		def BIT_search(self, x):
			i = 0
			s = 0
			step = 1 << self.size.bit_length() - 1
			while step:
				if i + step <= self.size and s + self.BIT[i + step] < x:
					i += step
					s += self.BIT[i]
				step >>= 1
			return i + 1
	BIT = BinaryIndexedTree(N, 0)
	ans = 0
	for (i, num) in enumerate(nl):
		l = BIT.BIT_query(num)
		BIT.BIT_update(num, 1)
		r = i - l
		a = BIT.BIT_search(l - 1) if l >= 2 else 0
		b = BIT.BIT_search(l) if l >= 1 else 0
		d = BIT.BIT_search(l + 2) if r >= 1 else N + 1
		e = BIT.BIT_search(l + 3) if r >= 2 else N + 1
		ret = 0
		if b != 0:
			ret += (b - a) * (d - num)
		if d != 0:
			ret += (e - d) * (num - b)
		ans += ret * (N - i)
	print(ans)
main()


class BIT:

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

	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, x):
		sum_ = 0
		pos = 0
		for i in range(self.depth + 1)[::-1]:
			k = pos + (1 << i)
			if k <= self.size and sum_ + self.tree[k] < x:
				sum_ += self.tree[k]
				pos += 1 << i
		return (pos + 1, sum_)
N = int(input())
l = [(j, i) for (i, j) in enumerate(map(int, input().split()))]
l.sort(key=lambda x: -x[0])
tree = BIT(N)
m = [0] * N
ans = 0
for (value, idx) in l:
	v = tree.sum(idx + 1)
	a = tree.lower_bound(v - 1)[0] if v > 1 else 0
	b = tree.lower_bound(v - 0)[0] if v else 0
	c = tree.lower_bound(v + 1)[0]
	d = tree.lower_bound(v + 2)[0]
	tree.add(idx + 1, 1)
	idx += 1
	ans += ((b - a) * (c - idx) + (d - c) * (idx - b)) * value
print(ans)


def examA():
	N = I()
	ans = 0
	print(ans)
	return

def examB():
	ans = 0
	print(ans)
	return

def examC():
	ans = 0
	print(ans)
	return

def examD():
	ans = 0
	print(ans)
	return

def examE():

	class Bit:

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

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

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

		def search(self, x):
			i = 0
			s = 0
			step = 1 << self.size.bit_length() - 1
			while step:
				if i + step <= self.size and s + self.tree[i + step] < x:
					i += step
					s += self.tree[i]
				step >>= 1
			return i + 1

		def debug(self, k):
			return [self.sum(i) for i in range(k)]
	N = I()
	P = LI()
	Order = [[i + 1] for i in range(N)]
	for (i, p) in enumerate(P):
		Order[i].append(p)
	Order.sort(key=lambda x: x[1], reverse=True)
	ans = 0
	bit = Bit(N + 2)
	for (i, p) in Order:
		L = bit.sum(i)
		R = bit.sum(N) - L
		bit.add(i)
		(l0, l1, r0, r1) = (0, 0, N + 1, N + 1)
		if L >= 2:
			l0 = bit.search(L - 1)
		if L >= 1:
			l1 = bit.search(L)
		if R >= 1:
			r0 = bit.search(L + 2)
		if R >= 2:
			r1 = bit.search(L + 3)
		cnt = 0
		if l1 > 0:
			cnt += (l1 - l0) * (r0 - i)
		if r0 > 0:
			cnt += (i - l1) * (r1 - r0)
		ans += cnt * p
	print(ans)
	return

def examF():

	def bfs(n, e, S):
		W = [0] * 2 ** n
		cur = 1
		que = deque()
		que.append(e)
		while cur < 2 ** n:
			now = que.popleft()
			depth = W[now]
			if S[now] <= S[cur]:
				return 'No'
			for ne in range(n - depth):
				cur += 1
				W[now + 1 + ne] = depth + 1
				que.append(now + 1 + ne)
		return 'Yes'
	N = I()
	S = LI()
	S.sort(reverse=True)
	ans = bfs(N, 0, S)
	print(ans)
	return
import sys, copy, bisect, itertools, heapq, math
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
alphabet = [chr(ord('a') + i) for i in range(26)]
examE()


n = int(input())
p = list(map(int, input().split()))
pos_list = [0] * n
for (index, i) in enumerate(p, 0):
	pos_list[i - 1] = index
left_next_index = list(range(-1, n - 1)) + [-1, -1]
right_next_index = list(range(1, n + 1)) + [n, n]
answer = 0
for i in range(1, n):
	index = pos_list[i - 1]
	l1 = left_next_index[index]
	l2 = left_next_index[l1]
	r1 = right_next_index[index]
	r2 = right_next_index[r1]
	answer += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 - l2))
	left_next_index[r1] = l1
	right_next_index[l1] = r1
print(answer)


n = int(input())
aa = list(map(int, input().split()))
ans = 0
pos = [0] * (n + 1)
for (i, a) in enumerate(aa):
	pos[a] = i + 2
Lnext = [1, 1] + list(range(1, n + 1)) + [n, n]
Rnext = [3, 3] + list(range(3, n + 3)) + [n + 2, n + 2]
for a in range(1, n + 1):
	i = pos[a]
	l0 = Lnext[i]
	l1 = Lnext[l0]
	r0 = Rnext[i]
	r1 = Rnext[r0]
	ans += a * ((l0 - l1) * (r0 - i) + (i - l0) * (r1 - r0))
	Lnext[r0] = l0
	Rnext[l0] = r0
print(ans)


from sys import stdin
n = int(stdin.readline().rstrip())
p = list(map(int, stdin.readline().rstrip().split()))

def get_nexts(p):
	(d, e) = ([n for i in range(n)], [n for i in range(n)])
	(stack1, stack2) = ([], [])
	for i in range(n):
		while stack2 and p[stack2[-1]] < p[i]:
			idx = stack2.pop()
			e[idx] = i
		to_append = []
		while stack1 and p[stack1[-1]] < p[i]:
			idx = stack1.pop()
			d[idx] = i
			to_append.append(idx)
		while to_append:
			stack2.append(to_append.pop())
		stack1.append(i)
	(dist1, dist2) = ([], [])
	for i in range(n):
		dist1.append(d[i] - i)
		dist2.append(e[i] - d[i])
	return (dist1, dist2)
(dist1, dist2) = get_nexts(p)
(dist3, dist4) = get_nexts(p[::-1])
ans = 0
for i in range(n):
	ans += (dist1[i] * dist4[n - 1 - i] + dist2[i] * dist3[n - 1 - i]) * p[i]
print(ans)


from collections import deque
from bisect import bisect_left
N = int(input())
P = list(map(int, input().split()))
big = []
for k in range(N):
	big.append((P[k], k + 1))
big.sort(key=lambda x: x[0], reverse=True)
big = deque(big)
item = big.popleft()
done = [0, 0, item[1], N + 1, N + 1]
ans = 0
while big:
	item = big.popleft()
	index = item[1]
	num = item[0]
	i = bisect_left(done, index)
	done.insert(i, index)
	ans += num * ((done[i + 2] - done[i + 1]) * (index - done[i - 1]) + (done[i - 1] - done[i - 2]) * (done[i + 1] - index))
print(ans)


class BinaryIndexedTree:

	def __init__(self, N):
		self.N = N
		self.arr = [0] * (N + 1)

	def query(self, i):
		ret = 0
		i += 1
		while i:
			ret += self.arr[i]
			lsb = i & -i
			i -= lsb
		return ret

	def add(self, i, v):
		i += 1
		while i < self.N + 1:
			lsb = i & -i
			self.arr[i] += v
			i += lsb

	def search(self, x):
		lo = -1
		hi = self.N
		while lo < hi:
			mid = (lo + hi) // 2
			if self.query(mid) < x:
				lo = mid + 1
			else:
				hi = mid
		return lo

def main():
	N = int(input())
	P = list(map(int, input().split()))
	idx = [0] * N
	bit = BinaryIndexedTree(N)
	for i in range(N):
		idx[P[i] - 1] = i
	ans = 0
	for i in range(N)[::-1]:
		bit.add(idx[i], 1)
		x = bit.query(idx[i])
		l = bit.search(x - 1)
		ll = bit.search(x - 2)
		r = bit.search(x + 1)
		rr = bit.search(x + 2)
		tmp = (idx[i] - l) * (rr - r) + (r - idx[i]) * (l - ll)
		ans += (i + 1) * tmp
	print(ans)
main()


N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x: x[1])
before_idx = list(range(-1, N - 1)) + [-1, -1]
next_idx = list(range(1, N + 1)) + [N, N]
ans = 0
for (i, p) in P:
	il1 = before_idx[i]
	il2 = before_idx[il1]
	ir1 = next_idx[i]
	ir2 = next_idx[ir1]
	ans += p * ((i - il1) * (ir2 - ir1) + (ir1 - i) * (il1 - il2))
	before_idx[ir1] = il1
	next_idx[il1] = ir1
print(ans)


import bisect

class SqrtSet:

	def __init__(self, block_limit=201):
		self.key = []
		self.child = [[]]
		self.block_limit = block_limit

	def search_lower(self, key):
		if key is None:
			return None
		ret = None
		i = bisect.bisect_left(self.key, key)
		if i != 0:
			ret = self.key[i - 1]
		block = self.child[i]
		i = bisect.bisect_left(block, key)
		if i != 0:
			ret = block[i - 1]
		return ret

	def search_higher(self, key):
		if key is None:
			return None
		ret = None
		i = bisect.bisect_right(self.key, key)
		if i != len(self.key):
			ret = self.key[i]
		block = self.child[i]
		i = bisect.bisect_right(block, key)
		if i != len(block):
			ret = block[i]
		return ret

	def insert(self, key):
		i = bisect.bisect(self.key, key)
		block = self.child[i]
		bisect.insort(block, key)
		if len(block) == self.block_limit:
			sep = self.block_limit // 2
			self.key.insert(i, block[sep])
			self.child.insert(i + 1, block[sep + 1:])
			self.child[i] = block[:sep]

	def dump(self):
		for b in self.child:
			print(len(b), end=' ')
		print('')

def main():
	n = int(input())
	p = list(map(int, input().split()))
	idx = [0] * n
	for i in range(0, n):
		idx[i] = i
	idx.sort(key=lambda i: -p[i])
	t = SqrtSet()
	t.insert(-1)
	t.insert(n)
	ans = 0
	for i in idx:
		nex = t.search_higher(i)
		nexnex = t.search_higher(nex)
		pre = t.search_lower(i)
		prepre = t.search_lower(pre)
		if prepre != None:
			ans += p[i] * (pre - prepre) * (nex - i)
		if nexnex != None:
			ans += p[i] * (i - pre) * (nexnex - nex)
		t.insert(i)
	print(ans)
main()


from operator import itemgetter

def solve(n, ppp):
	qqq = sorted(enumerate(ppp), key=itemgetter(1))
	left_next_index = list(range(-1, n - 1)) + [-1, -1]
	right_next_index = list(range(1, n + 1)) + [n, n]
	ans = 0
	for (i, p) in qqq:
		l2 = left_next_index[i]
		l1 = left_next_index[l2]
		r1 = right_next_index[i]
		r2 = right_next_index[r1]
		ans += p * ((l2 - l1) * (r1 - i) + (r2 - r1) * (i - l2))
		left_next_index[r1] = l2
		right_next_index[l2] = r1
	return ans
n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))


N = int(input())
P = map(int, input().split())
pos = {}
for (i, p) in enumerate(P):
	pos[p] = i + 1
foll = [i + 1 for i in range(N + 1)] + [N + 1]
prev = [0] + [i for i in range(N + 1)]
ans = 0
for i in range(1, N + 1):
	curr = pos[i]
	r = foll[curr]
	rr = foll[r]
	l = prev[curr]
	ll = prev[l]
	ans += (l - ll) * (r - curr) * i
	ans += (rr - r) * (curr - l) * i
	foll[l] = foll[curr]
	prev[r] = prev[curr]
print(ans)


import sys

def main():
	input = sys.stdin.readline
	N = int(input().strip())
	P = list(map(int, input().strip().split()))
	RR = [i + 1 for i in range(N)]
	LL = [i - 1 for i in range(N)]
	ips = [0] * N
	for (i, val) in enumerate(P):
		ips[val - 1] = i
	P.sort()
	x = 0
	for i in range(N):
		target = ips[P[i] - 1]
		R1ind = RR[target]
		R2ind = RR[min(R1ind, N - 1)]
		L1ind = LL[target]
		L2ind = LL[max(L1ind, 0)]
		x += ((L1ind - L2ind) * (R1ind - target) + (target - L1ind) * (R2ind - R1ind)) * P[i]
		if L1ind != -1:
			RR[L1ind] = R1ind
		if R1ind != N:
			LL[R1ind] = L1ind
	print(x)
main()


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:

	def __init__(self, n):
		nv = 1
		while nv < n:
			nv *= 2
		self.size = nv
		self.tree = [0] * nv

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

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

	def get(self, l, r=None):
		if r is None:
			r = l + 1
		res = 0
		if r:
			res += self.sum(r - 1)
		if l:
			res -= self.sum(l - 1)
		return res

	def bisearch_left(self, l, r, x):
		l_sm = self.sum(l - 1)
		ok = r + 1
		ng = l - 1
		while ng + 1 < ok:
			mid = (ok + ng) // 2
			if self.sum(mid) - l_sm >= x:
				ok = mid
			else:
				ng = mid
		if ok != r + 1:
			return ok
		else:
			return -1

	def bisearch_right(self, l, r, x):
		r_sm = self.sum(r)
		ok = l - 1
		ng = r + 1
		while ok + 1 < ng:
			mid = (ok + ng) // 2
			if r_sm - self.sum(mid - 1) >= x:
				ok = mid
			else:
				ng = mid
		if ok != l - 1:
			return ok
		else:
			return -1
N = INT()
A = LIST()
idxs = [0] * (N + 1)
for (i, a) in enumerate(A):
	idxs[a] = i + 1
bit = BIT(N + 2)
bit.add(0, 2)
bit.add(N + 1, 2)
ans = [0] * (N + 1)
for a in range(N, 0, -1):
	idx = idxs[a]
	p = bit.bisearch_right(0, idx, 2) + 1
	q = bit.bisearch_right(0, idx, 1) + 1
	r = bit.bisearch_left(idx, N + 1, 1) - 1
	s = bit.bisearch_left(idx, N + 1, 2) - 1
	ans[a] = ((q - p) * (r - idx + 1) + (idx - q + 1) * (s - r)) * a
	bit.add(idx, 1)
print(sum(ans))


def main():
	N = int(input())
	(*p,) = list(map(int, input().split()))
	xtoi = [-1] * (N + 1)
	for (i, x) in enumerate(p):
		xtoi[x] = i
	L = [-1] * (N + 2)
	R = [N] * (N + 2)
	for i in range(N):
		L[i] = i - 1
		R[i] = i + 1
	iter_inds = iter(xtoi)
	next(iter_inds)
	ans = 0
	for (x, ind) in enumerate(iter_inds, start=1):
		l1 = L[ind]
		l2 = L[l1]
		r1 = R[ind]
		r2 = R[r1]
		ans += x * ((l1 - l2) * (r1 - ind) + (r2 - r1) * (ind - l1))
		L[r1] = l1
		R[l1] = r1
	print(ans)

def __starting_point():
	main()
__starting_point()


from bisect import *

class SqrtSet:

	def __init__(self, block_limit=201):
		self.key = []
		self.child = [[]]
		self.block_limit = block_limit

	def le(self, key):
		ret = key
		i = bisect_left(self.key, key)
		if i:
			ret = self.key[i - 1]
		block = self.child[i]
		i = bisect_left(block, key)
		if i:
			ret = block[i - 1]
		return ret

	def ge(self, key):
		ret = key
		i = bisect(self.key, key)
		if i < len(self.key):
			ret = self.key[i]
		block = self.child[i]
		i = bisect(block, key)
		if i < len(block):
			ret = block[i]
		return ret

	def insert(self, key):
		i = bisect(self.key, key)
		block = self.child[i]
		insort(block, key)
		if len(block) == self.block_limit:
			sep = self.block_limit // 2
			self.key.insert(i, block[sep])
			self.child.insert(i + 1, block[sep + 1:])
			self.child[i] = block[:sep]

def main():
	(n, *p) = map(int, open(0).read().split())
	l = [0] * n
	for (i, v) in enumerate(p, 1):
		l[v - 1] = i
	t = SqrtSet()
	(insert, le, ge) = (t.insert, t.le, t.ge)
	(insert(0), insert(n + 1))
	a = 0
	for (i, v) in list(enumerate(l, 1))[::-1]:
		(f, b) = (ge(v), le(v))
		(g, c) = (ge(f), le(b))
		a += i * ((f - v) * (b - c) + (v - b) * (g - f))
		insert(v)
	print(a)
main()


n = int(input())
A = list(map(int, input().split()))
A = [a - 1 for a in A]
P = [-1] * n
for (i, a) in enumerate(A):
	P[a] = i
R = [[n] * 2 for _ in range(n)]
q = []
import heapq
heapq.heapify(q)
for i in range(n):
	temp = []
	while q:
		if q[0][0] < A[i]:
			(v, j) = heapq.heappop(q)
			R[v][j] = i
			if j == 0:
				temp.append((v, j + 1))
		else:
			break
	heapq.heappush(q, (A[i], 0))
	for (v, j) in temp:
		heapq.heappush(q, (v, j))
L = [[-1] * 2 for _ in range(n)]
q = []
import heapq
heapq.heapify(q)
for i in reversed(list(range(n))):
	temp = []
	while q:
		if q[0][0] < A[i]:
			(v, j) = heapq.heappop(q)
			L[v][j] = i
			if j == 0:
				temp.append((v, j + 1))
		else:
			break
	heapq.heappush(q, (A[i], 0))
	for (v, j) in temp:
		heapq.heappush(q, (v, j))
ans = 0
for i in range(n - 1):
	p = P[i]
	l1 = L[i][0]
	l2 = L[i][1]
	r1 = R[i][0]
	r2 = R[i][1]
	ans += ((l1 - l2) * (r1 - p) + (r2 - r1) * (p - l1)) * (i + 1)
print(ans)


N = int(input())
P = list(map(int, input().split()))
I = [0] * N
for (i, p) in enumerate(P):
	I[N - p] = i

class BIT:

	def __init__(self, size):
		self.N = size
		self.v = [0] * (self.N + 1)

	def add(self, i, x):
		i += 1
		while i <= self.N:
			self.v[i] += x
			i += i & -i

	def sum(self, a, b=0):
		if a > b:
			(a, b) = (b, a)
		if a > 0:
			r = self.sum(b) - self.sum(a)
		else:
			r = 0
			i = b
			while i > 0:
				r += self.v[i]
				i -= i & -i
		return r

	def right(self, x):
		(a, b) = (x + 1, self.N)
		while a + 1 < b:
			t = (a + b) // 2
			if self.sum(a, t) > 0:
				b = t
			else:
				a = t
		return a

	def left(self, x):
		(a, b) = (0, x)
		while a + 1 < b:
			t = (a + b) // 2
			if self.sum(t, b) > 0:
				a = t
			else:
				b = t
		return a
b = BIT(2 ** 17)
b.add(0, N + 1)
b.add(1, N + 1)
b.add(N + 2, N + 1)
b.add(N + 3, N + 1)
a = 0
p = N
for i in I:
	l = b.left(i + 2)
	ll = b.left(l)
	r = b.right(i + 2)
	rr = b.right(r)
	if 1 < l and r < N + 2:
		a += ((l - ll) * (r - i - 2) + (rr - r) * (i + 2 - l)) * p
	elif 1 < l:
		a += (l - ll) * (N - i) * p
	elif r < N + 2:
		a += (rr - r) * (i + 1) * p
	b.add(i + 2, p)
	p -= 1
print(a)


class BIT:

	def __init__(self, n):
		self.N = n
		self.n = 1 << n.bit_length()
		self.data = [0] * (self.n + 1)
		self.num = 0

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

	def add(self, i, x):
		while i <= self.n:
			self.data[i] += x
			i += i & -i
		self.num += 1

	def search(self, value):
		if value < 1:
			return 0
		if value > self.num:
			return self.N + 1
		(x, sx) = (0, 0)
		step = self.n
		while step:
			y = x + step
			sy = sx + self.data[y]
			if sy < value:
				(x, sx) = (y, sy)
			step >>= 1
		return x + 1
N = int(input())
P = list(map(int, input().split()))
index = [-1] * N
BIT = BIT(N)
ans = 0
for i in range(N):
	index[P[i] - 1] = i + 1
for (num, p) in enumerate(range(N, 0, -1)):
	i = index[p - 1]
	BIT.add(i, 1)
	j = BIT.sum(i - 1) + 1
	a = BIT.search(j - 2)
	b = BIT.search(j - 1)
	c = BIT.search(j + 1)
	d = BIT.search(j + 2)
	ans += p * ((b - a) * (c - i) + (d - c) * (i - b))
print(ans)


import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines
import bisect

def main():
	(n, *p) = map(int, read().split())
	H = [0, 0, n + 1, n + 1]
	pidx = [0] * (n + 1)
	for i in range(n):
		pidx[p[i]] = i + 1
	pidx.reverse()
	ans = 0
	for i in pidx:
		I = bisect.bisect_left(H, i)
		ans += p[i - 1] * ((H[I - 1] - H[I - 2]) * (H[I] - i) + (H[I + 1] - H[I]) * (i - H[I - 1]))
		H.insert(I, i)
	print(ans)
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
P = [None] + [int(x) for x in input().split()]
p_to_i = [None] * (N + 1)
for (i, x) in enumerate(P[1:], 1):
	p_to_i[x] = i

def BIT_add(i):
	while i <= N:
		tree[i] += 1
		i += i & -i

def BIT_sum(i):
	s = 0
	while i:
		s += tree[i]
		i -= i & -i
	return s

def BIT_search(x):
	left = 0
	right = N
	while right - left > 1:
		mid = (left + right) // 2
		if BIT_sum(mid) >= x:
			right = mid
		else:
			left = mid
	return right
tree = [0] * (N + 1)
answer = 0
for x in range(N, 0, -1):
	c = p_to_i[x]
	L = BIT_sum(c)
	BIT_add(c)
	R = N - x - L
	a = BIT_search(L - 1) if L >= 2 else 0
	b = BIT_search(L) if L >= 1 else 0
	d = BIT_search(L + 2) if R >= 1 else N + 1
	e = BIT_search(L + 3) if R >= 2 else N + 1
	coef = 0
	if b != 0:
		coef += (b - a) * (d - c)
	if d != 0:
		coef += (e - d) * (c - b)
	answer += x * coef
print(answer)


from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq
sys.setrecursionlimit(100000)

def rsa(sep=''):
	if sep == '':
		return input().split()
	else:
		return input().split(sep)

def rip(sep=''):
	if sep == '':
		return list(map(int, input().split()))
	else:
		return list(map(int, input().split(sep)))

def ria(sep=''):
	return list(rip(sep))

def ri():
	return int(input())

def rd():
	return float(input())

def rs():
	return input()

def main():
	N = ri()
	P = [N + 1, N + 1] + ria() + [N + 1, N + 1]
	ord = []
	for i in range(2, N + 2):
		ord.append((P[i], i))
	ord = sorted(ord)
	tot = 0
	l = [i for i in range(N + 4)]
	r = [i for i in range(N + 4)]
	used = [False] * (N + 4)
	for (v, idx) in ord:
		used[idx] = True
		if used[idx - 1]:
			l[idx] = l[idx - 1]
		if used[idx + 1]:
			r[idx] = r[idx + 1]
		r[l[idx]] = r[idx]
		l[r[idx]] = l[idx]
		l0 = l[idx] - 1
		r0 = r[idx] + 1
		l1 = l0 - 1 if not used[l0 - 1] else l[l0 - 1] - 1
		r1 = r0 + 1 if not used[r0 + 1] else r[r0 + 1] + 1
		if l1 != 0:
			rseg = r0 - idx
			lseg = l0 - l1
			tot += lseg * rseg * v
		if r1 != N + 3:
			rseg = r1 - r0
			lseg = idx - l0
			tot += lseg * rseg * v
	print(tot)

def __starting_point():
	main()
__starting_point()


import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

class BinaryIndexTree:

	def __init__(self, n):
		self.size = n
		self._container = [0] * (n + 1)
		self.depth = n.bit_length()

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

	def add(self, i, x):
		if i == 0:
			return
		while i <= self.size:
			self._container[i] += x
			i += i & -i

	def lower_bound(self, x):
		s = 0
		idx = 0
		for i in range(self.depth, -1, -1):
			k = idx + (1 << i)
			if k <= self.size and s + self._container[k] < x:
				s += self._container[k]
				idx += 1 << i
		return idx + 1

def main():
	n = int(readline())
	p = list(map(int, readline().split()))
	idx = dict()
	for (i, x) in enumerate(p):
		idx[x] = i + 1
	bt = BinaryIndexTree(n + 2)
	bt.add(n + 2, 2)
	bt.add(1, 2)
	ans = 0
	for num in range(n, 0, -1):
		i = idx[num]
		s = bt.sum(i + 1)
		l1 = bt.lower_bound(s)
		l2 = bt.lower_bound(s - 1)
		r1 = bt.lower_bound(s + 1)
		r2 = bt.lower_bound(s + 2)
		ans += num * (i + 1 - l1) * (r2 - r1)
		ans += num * (r1 - i - 1) * (l1 - l2)
		bt.add(i + 1, 1)
	print(ans)
main()


class SegmentTree:

	def __init__(self, array, f, ti):
		self.f = f
		self.ti = ti
		self.n = n = 2 ** len(array).bit_length()
		self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
		for i in range(n - 1, 0, -1):
			dat[i] = f(dat[i << 1], dat[i << 1 | 1])

	def update(self, p, v):
		(f, n, dat) = (self.f, self.n, self.dat)
		p += n
		dat[p] = v
		while p > 1:
			p >>= 1
			dat[p] = f(dat[p << 1], dat[p << 1 | 1])

	def query(self, l, r):
		(f, ti, n, dat) = (self.f, self.ti, self.n, self.dat)
		res = ti
		l += n
		r += n
		while l < r:
			if l & 1:
				res = f(res, dat[l])
				l += 1
			if r & 1:
				r -= 1
				res = f(dat[r], res)
			l >>= 1
			r >>= 1
		return res
N = int(input())
P = [int(_) for _ in input().split()]
p_i = {p: i + 1 for (i, p) in enumerate(P)}
SL = SegmentTree([0] * (N + 2), max, 0)
SR = SegmentTree([N + 1] * (N + 2), min, N + 1)
ans = 0
for p in range(N, 0, -1):
	i = p_i[p]
	SL.update(i, i)
	SR.update(i, i)
	il = SL.query(0, i)
	ir = SR.query(i + 1, N + 2)
	if il > 0:
		ill = SL.query(0, il)
		ans += p * (il - ill) * (ir - i)
	if ir < N + 1:
		irr = SR.query(ir + 1, N + 2)
		ans += p * (irr - ir) * (i - il)
print(ans)


class BIT(object):
	from operator import add

	def __init__(self, A, f=add):
		N = len(A)
		self.__len = N
		self.__f = f
		self.__bit = A[:]
		for i in range(N):
			j = i + (i + 1 & -(i + 1))
			if j < N:
				self.tree[j] = self.func(self.tree[i], self.tree[j])

	def __repr__(self):
		return str(self.tree)

	@property
	def func(self):
		return self.__f

	@property
	def tree(self):
		return self.__bit

	def add(self, i, w):
		while i < self.__len:
			self.tree[i] = self.func(self.tree[i], w)
			i += i + 1 & -(i + 1)

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

	def bisect_left(self, w):
		if w > self.sum(self.__len - 1):
			return self.__len
		elif self.__len == 1:
			return 0
		n = 2 ** ((self.__len - 1).bit_length() - 1)
		res = 0
		while n:
			if res + n - 1 > self.__len - 1:
				n //= 2
				continue
			if w <= self.tree[res + n - 1]:
				n //= 2
			else:
				w -= self.tree[res + n - 1]
				res += n
				n //= 2
		return res

	def bisect_right(self, w):
		if w >= self.sum(self.__len - 1):
			return self.__len
		elif self.__len == 1:
			return 0
		n = 2 ** ((self.__len - 1).bit_length() - 1)
		res = 0
		while n:
			if w < self.tree[res + n - 1]:
				n //= 2
			else:
				w -= self.tree[res + n - 1]
				res += n
				n //= 2
		return res
n = int(input())
A = list(map(int, input().split()))
idx = [0] * n
for (i, a) in enumerate(A):
	idx[a - 1] = i
bit = BIT([0] * n)
score = 0
for k in range(n, 0, -1):
	i = idx[k - 1]
	bit.add(i, 1)
	s = bit.sum(i)
	l0 = bit.bisect_left(s - 1.5) - (s <= 1)
	l1 = bit.bisect_left(s - 2.5) - (s <= 2)
	r0 = bit.bisect_left(s + 0.5)
	r1 = bit.bisect_left(s + 1.5)
	score += k * ((l0 - l1) * (r0 - i) + (r1 - r0) * (i - l0))
print(score)


import heapq
from collections import defaultdict
N = int(input())
P = list(map(int, input().split()))
d_r = defaultdict(lambda : N + 1)
h_r = []
d_r2 = defaultdict(lambda : N + 1)
h_r2 = []
for i in range(N):
	p = P[i]
	while h_r2:
		q = heapq.heappop(h_r2)
		if q < p:
			d_r2[q] = p
		else:
			heapq.heappush(h_r2, q)
			break
	while h_r:
		q = heapq.heappop(h_r)
		if q < p:
			d_r[q] = p
			heapq.heappush(h_r2, q)
		else:
			heapq.heappush(h_r, q)
			break
	heapq.heappush(h_r, p)
d_l = defaultdict(lambda : 0)
h_l = []
d_l2 = defaultdict(lambda : 0)
h_l2 = []
for i in range(N - 1, -1, -1):
	p = P[i]
	while h_l2:
		q = heapq.heappop(h_l2)
		if q < p:
			d_l2[q] = p
		else:
			heapq.heappush(h_l2, q)
			break
	while h_l:
		q = heapq.heappop(h_l)
		if q < p:
			d_l[q] = p
			heapq.heappush(h_l2, q)
		else:
			heapq.heappush(h_l, q)
			break
	heapq.heappush(h_l, p)
d = {}
for i in range(N):
	d[P[i]] = i
d[N + 1] = N
d[0] = -1
ans = 0
for i in range(N):
	x = d[d_l2[P[i]]]
	y = d[d_l[P[i]]]
	z = d[d_r[P[i]]]
	w = d[d_r2[P[i]]]
	ans += P[i] * ((y - x) * (z - i) + (w - z) * (i - y))
print(ans)


class BIT:

	def __init__(self, n):
		self.n = n
		self.dat = [0] * n

	def add(self, k, a):
		while k < self.n:
			self.dat[k] += a
			k |= k + 1

	def sum(self, k):
		s = 0
		while k >= 0:
			s += self.dat[k]
			k = (k & k + 1) - 1
		return s
N = int(input())
P = [int(x) for x in input().split()]
pos = [0] * (N + 1)
for i in range(N):
	pos[P[i]] = i
bit = BIT(N)
ans = 0
for i in range(N, 0, -1):
	bit.add(pos[i], 1)
	s = bit.sum(pos[i])
	bound = []
	for s2 in [s - 2, s - 1, s + 1, s + 2]:
		if s2 <= 0:
			bound.append(-1)
			continue
		(ok, ng) = (N, -1)
		while ok - ng > 1:
			mid = ok + ng >> 1
			if bit.sum(mid) >= s2:
				ok = mid
			else:
				ng = mid
		bound.append(ok)
	res = (bound[1] - bound[0]) * (bound[2] - pos[i]) + (pos[i] - bound[1]) * (bound[3] - bound[2])
	ans += i * res
print(ans)


N = int(input())
P = [None] + list(map(int, input().split()))
p_to_index = [None] * (N + 1)
for (index, x) in enumerate(P[1:], 1):
	p_to_index[x] = index

def BIT_add(i):
	while i <= N:
		tree[i] += 1
		i += i & -i

def BIT_sum(i):
	s = 0
	while i:
		s += tree[i]
		i -= i & -i
	return s

def BIT_search(x):
	i = 0
	s = 0
	step = 1 << N.bit_length() - 1
	while step:
		if i + step <= N and s + tree[i + step] < x:
			i += step
			s += tree[i]
		step >>= 1
	return i + 1
tree = [0] * (N + 1)
ans = 0
for x in range(N, 0, -1):
	c = p_to_index[x]
	L = BIT_sum(c)
	BIT_add(c)
	R = N - x - L
	a = BIT_search(L - 1) if L >= 2 else 0
	b = BIT_search(L) if L >= 1 else 0
	d = BIT_search(L + 2) if R >= 1 else N + 1
	e = BIT_search(L + 3) if R >= 2 else N + 1
	tmp = 0
	if b != 0:
		tmp += (b - a) * (d - c)
	if d != 0:
		tmp += (e - d) * (c - b)
	ans += tmp * x
print(ans)


n = int(input())
lst = list(enumerate(list(map(int, input().split()))))
sorted_lst = sorted(lst, key=lambda x: x[1])
left_next_index = list(range(-1, n - 1)) + [-1, -1]
right_next_index = list(range(1, n + 1)) + [n, n]
ans = 0
for (i, p) in sorted_lst:
	l2 = left_next_index[i]
	l1 = left_next_index[l2]
	r1 = right_next_index[i]
	r2 = right_next_index[r1]
	a = p * ((l2 - l1) * (r1 - i) + (r2 - r1) * (i - l2))
	ans += a
	left_next_index[r1] = l2
	right_next_index[l2] = r1
print(ans)


class Bit:

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

	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, x):
		sum_ = 0
		pos = 0
		for i in range(self.depth, -1, -1):
			k = pos + (1 << i)
			if k <= self.size and sum_ + self.tree[k] < x:
				sum_ += self.tree[k]
				pos += 1 << i
		return (pos + 1, sum_)

	def get_less_than_x_cnt(self, x):
		(lb_pos, lb_sum) = self.lower_bound(x)
		return lb_pos - 1

	def get_less_than_and_x_cnt(self, x):
		(lb_pos, lb_sum) = self.lower_bound(x + 1)
		return lb_pos - 1

	def get_more_than_x_cnt(self, x):
		return self.size - self.get_less_than_and_x_cnt(x)
n = int(input())
pl = list(map(int, input().split()))
pll = []
for (i, p) in enumerate(pl):
	pll.append((p, i + 2))
pll.sort(reverse=True)
bit = Bit(n + 1)
bit.add(1, 1)
ans = 0
for (p, i) in pll:
	ix = bit.sum(i)
	(lmax, _) = bit.lower_bound(ix)
	(lmin, _) = bit.lower_bound(ix - 1)
	lcnt = lmax - lmin
	(rmin, _) = bit.lower_bound(ix + 1)
	(rmax, _) = bit.lower_bound(ix + 2)
	rcnt = rmax - rmin
	comb = lcnt * (rmin - i) + (i - lmax) * rcnt
	ans += comb * p
	bit.add(i, 1)
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
P = list(map(int, input().split()))
A = [[P[i], i] for i in range(len(P))]
A.sort(reverse=True)

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
B = Bit(n + 1)
L0 = [[0] * 2 for i in range(n)]
for i in range(n):
	ind = A[i][1]
	B.add(ind + 1, 1)
	s = B.sum(ind + 1)
	R = [-1, -1]
	for j in range(2):
		l = -1
		r = ind + 1
		m = (l + r + 1) // 2
		while r - l > 1:
			if B.sum(m) < s - 1 - j:
				l = m
			else:
				r = m
			m = (l + r + 1) // 2
		R[j] = r
	L0[i] = [ind + 1 - R[0], R[0] - R[1]]
B = Bit(n + 1)
L1 = [[0] * 2 for i in range(n)]
for i in range(n):
	ind = n - 1 - A[i][1]
	B.add(ind + 1, 1)
	s = B.sum(ind + 1)
	R = [-1, -1]
	for j in range(2):
		l = -1
		r = ind + 1
		m = (l + r + 1) // 2
		while r - l > 1:
			if B.sum(m) < s - 1 - j:
				l = m
			else:
				r = m
			m = (l + r + 1) // 2
		R[j] = r
	L1[i] = [ind + 1 - R[0], R[0] - R[1]]
ans = 0
for i in range(n):
	ans += (n - i) * (L0[i][0] * L1[i][1] + L0[i][1] * L1[i][0])
print(ans)


def main():
	n = int(input())
	xx = list(map(int, input().split()))
	pp = [(xx[i], i + 1) for i in range(n)]
	pp.sort(key=lambda x: x[0])
	left = [0, 0] + [i + 1 for i in range(n)]
	right = [i + 1 for i in range(n)] + [n + 1, n + 1]
	ans = 0
	for i in range(n):
		(ori_num, ori_ind) = pp[i]
		l1 = left[ori_ind]
		l2 = left[l1]
		r1 = right[ori_ind]
		r2 = right[r1]
		ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num
		right[l1] = r1
		left[r1] = l1
	print(ans)
main()


import bisect

class BTreeNode:

	def __init__(self):
		self.key = []
		self.child = []

class BTree:

	def __init__(self):
		self.root = BTreeNode()

	def search_higher(self, key):
		ptr = self.root
		ret = None
		while ptr.child:
			i = bisect.bisect_right(ptr.key, key)
			if i != len(ptr.key):
				ret = ptr.key[i]
			ptr = ptr.child[i]
		i = bisect.bisect_right(ptr.key, key)
		if i != len(ptr.key):
			ret = ptr.key[i]
		return ret

	def search_lower(self, key):
		ptr = self.root
		ret = None
		while ptr.child:
			i = bisect.bisect_left(ptr.key, key)
			if i != 0:
				ret = ptr.key[i - 1]
			ptr = ptr.child[i]
		i = bisect.bisect_left(ptr.key, key)
		if i != 0:
			ret = ptr.key[i - 1]
		return ret

	def insert(self, key):

		def insert_rec(ptr):
			b_size = 512
			if not ptr.child:
				bisect.insort(ptr.key, key)
				if len(ptr.key) == b_size * 2 - 1:
					ret = BTreeNode()
					ret.key = ptr.key[:b_size]
					ptr.key = ptr.key[b_size:]
					return ret
			else:
				i = bisect.bisect(ptr.key, key)
				temp = insert_rec(ptr.child[i])
				if temp is not None:
					ptr.key.insert(i, temp.key.pop(-1))
					ptr.child.insert(i, temp)
					if len(ptr.child) == b_size * 2:
						ret = BTreeNode()
						ret.child = ptr.child[:b_size]
						ptr.child = ptr.child[b_size:]
						ret.key = ptr.key[:b_size]
						ptr.key = ptr.key[b_size:]
						return ret
			return None
		temp = insert_rec(self.root)
		if temp is not None:
			root = BTreeNode()
			root.key = [temp.key.pop(-1)]
			root.child = [temp, self.root]
			self.root = root

	def dump(self):

		def dump_rec(ptr, dep):
			for _ in range(0, dep):
				print('  ', end='')
			print(ptr.key)
			for c in ptr.child:
				dump_rec(c, dep + 1)
		dump_rec(self.root, 0)
		print('')

def main():
	n = int(input())
	p = list(map(int, input().split()))
	idx = [0] * n
	for i in range(0, n):
		idx[i] = i
	idx.sort(key=lambda i: -p[i])
	t = BTree()
	t.insert(-1)
	t.insert(n)
	ans = 0
	for i in idx:
		nex = t.search_higher(i)
		nexnex = t.search_higher(nex)
		pre = t.search_lower(i)
		prepre = t.search_lower(pre)
		if prepre != None:
			ans += p[i] * (pre - prepre) * (nex - i)
		if nexnex != None:
			ans += p[i] * (i - pre) * (nexnex - nex)
		t.insert(i)
	print(ans)
main()


class BIT:

	def __init__(self, n):
		self.n = n
		self.N = 1 << n.bit_length()
		self.data = [0] * (self.N + 1)

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

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

	def search(self, w):
		if w <= 0:
			return 0
		x = 0
		k = self.N >> 1
		while k > 0:
			if x + k <= self.N and self.data[x + k] < w:
				w -= self.data[x + k]
				x += k
			k = k >> 1
		return x + 1

	def len(self):
		return self.data[self.N]
n = int(input())
p = list(map(int, input().split()))
index = [0] * (n + 1)
for i in range(n):
	index[p[i]] = i + 1
used = BIT(n)
result = 0
for i in range(1, n + 1)[::-1]:
	x = index[i]
	if used.len() == 0:
		used.add(x, 1)
		continue
	dx = used.sum(x)
	if dx > 0:
		lbl = 1
		if dx > 1:
			lbl = used.search(dx - 1) + 1
		lbr = used.search(dx)
		rbl = n
		if used.len() != dx:
			rbl = used.search(dx + 1) - 1
		result += (lbr - lbl + 1) * (rbl - x + 1) * i
	if dx < used.len():
		rbr = n
		if dx < used.len() - 1:
			rbr = used.search(dx + 2) - 1
		rbl = used.search(dx + 1)
		lbr = 1
		if dx > 0:
			lbr = used.search(dx) + 1
		result += (rbr - rbl + 1) * (x - lbr + 1) * i
	used.add(x, 1)
print(result)


n = int(input())
P = [int(i) for i in input().split()]
n_max = 10 ** 5
nn = n_max.bit_length() + 1
BIT = [0] * 2 ** nn
BIT.insert(0, 0)

def bitsum(BIT, i):
	s = 0
	while i > 0:
		s += BIT[i]
		i -= i & -i
	return s

def bitadd(BIT, i, x):
	while i <= 2 ** nn:
		BIT[i] += x
		i += i & -i
	return BIT

def bitlb(BIT, s):
	if s <= 0:
		return 0
	else:
		ret = 0
		k = 2 ** nn
		while k > 0:
			if k + ret <= 2 ** nn and BIT[k + ret] < s:
				s -= BIT[k + ret]
				ret += k
			k //= 2
		return ret + 1
D = dict()
for i in range(n):
	D[P[i]] = i + 1
PP = sorted(P, reverse=True)
bitadd(BIT, D[PP[0]], 1)
ans = 0
for i in range(1, n):
	cur = D[PP[i]]
	bitadd(BIT, cur, 1)
	tot = bitsum(BIT, cur)
	(l2, l1, r1, r2) = (bitlb(BIT, tot - 2), bitlb(BIT, tot - 1), min(n + 1, bitlb(BIT, tot + 1)), min(n + 1, bitlb(BIT, tot + 2)))
	add = PP[i] * ((-l1 + cur) * (r2 - r1) + (l1 - l2) * (r1 - cur))
	ans += add
print(ans)


import sys, bisect as bs, collections as cl
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7
Max = sys.maxsize

def l():
	return list(map(int, input().split()))

def m():
	return map(int, input().split())

def onem():
	return int(input())

def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x) - 1):
		if aa != x[i + 1]:
			a.append([aa, su])
			aa = x[i + 1]
			su = 1
		else:
			su += 1
	a.append([aa, su])
	return a

def jo(x):
	return ' '.join(map(str, x))

def max2(x):
	return max(map(max, x))

def In(x, a):
	k = bs.bisect_left(a, x)
	if k != len(a) and a[k] == x:
		return True
	else:
		return False
n = onem()
p = [0] + l() + [n + 1]
ans = 0
a = [0 for i in range(n + 2)]
for i in range(n + 2):
	a[p[i]] = i
l = [set() for i in range(n + 2)]
r = [set() for i in range(n + 2)]
for i in range(n + 2):
	l[i].add(max(0, i - 1))
	l[i].add(max(0, i - 2))
	r[i].add(min(n + 1, i + 1))
	r[i].add(min(n + 1, i + 2))
for i in range(n + 1):
	m = a[i]
	(x2, x1, y1, y2) = (min(l[m]), max(l[m]), min(r[m]), max(r[m]))
	hoge = i * (abs((m - x1) * (y2 - y1)) + abs((y1 - m) * (x1 - x2)))
	ans += hoge
	r[x1].clear()
	r[x1].add(y1)
	r[x1].add(y2)
	l[y1].clear()
	l[y1].add(x1)
	l[y1].add(x2)
	r[x2].clear()
	r[x2].add(x1)
	r[x2].add(y1)
	l[y2].clear()
	l[y2].add(y1)
	l[y2].add(x1)
print(ans)


n = int(input())
p = list(map(int, input().split()))
p_ind = [(p[i], i + 1) for i in range(n)]
p_ind.sort(reverse=True)
max_n = 10 ** 5
div_n = int(max_n ** (1 / 2)) + 1
a = [[] for _ in range(div_n)]
a[0] = [0, 0]
a[(n + 1) // div_n].append(n + 1)
a[(n + 1) // div_n].append(n + 1)
a_count = [0] * div_n
a_count[0] += 2
a_count[(n + 1) // div_n] += 2
import bisect
ans = 0
for tmp in p_ind:
	(val, i) = tmp
	group = i // div_n
	j = bisect.bisect(a[group], i)
	if j > 1:
		left1 = a[group][j - 1]
		left2 = a[group][j - 2]
	elif j == 1:
		left1 = a[group][j - 1]
		lg = group - 1
		while True:
			if a_count[lg] > 0:
				break
			lg -= 1
		left2 = a[lg][-1]
	else:
		lg = group - 1
		while True:
			if a_count[lg] > 0:
				break
			lg -= 1
		if a_count[lg] >= 2:
			left1 = a[lg][-1]
			left2 = a[lg][-2]
		else:
			left1 = a[lg][-1]
			while True:
				lg -= 1
				if a_count[lg] > 0:
					break
			left2 = a[lg][-1]
	if a_count[group] >= j + 2:
		right1 = a[group][j]
		right2 = a[group][j + 1]
	elif a_count[group] >= j + 1:
		right1 = a[group][j]
		rg = group
		while True:
			rg += 1
			if a_count[rg] > 0:
				break
		right2 = a[rg][0]
	else:
		rg = group
		while True:
			rg += 1
			if a_count[rg] > 0:
				break
		if a_count[rg] >= 2:
			right1 = a[rg][0]
			right2 = a[rg][1]
		else:
			right1 = a[rg][0]
			while True:
				rg += 1
				if a_count[rg] > 0:
					break
			right2 = a[rg][0]
	ans += ((right2 - right1) * (i - left1) + (right1 - i) * (left1 - left2)) * val
	a[group].insert(j, i)
	a_count[group] += 1
print(ans)


N = int(input())
Pn = list(map(int, input().split()))
In = [0] * (N + 1)
for i in range(N):
	In[Pn[i]] = i + 1
cnt = 0
l = [0] + [i for i in range(N + 1)]
r = [i + 1 for i in range(N + 1)] + [N + 1]
for v in range(1, N + 1):
	i = In[v]
	l1 = l[i]
	l2 = l[l1]
	r1 = r[i]
	r2 = r[r1]
	cnt += ((l1 - l2) * (r1 - i) + (i - l1) * (r2 - r1)) * v
	l[r1] = l1
	r[l1] = r1
print(cnt)


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	n = I()
	print(n ** 3)
	return

def B():
	n = I()
	a = LI()
	b = LI()
	c = LI()
	ans = sum(b)
	for i in range(n - 1):
		x = a[i]
		y = a[i + 1]
		if y == x + 1:
			ans += c[x - 1]
	print(ans)
	return

def C():
	n = I()
	b = LI()
	b.append(float('inf'))
	a = [min(b[i], b[i - 1]) for i in range(n)]
	print(sum(a))
	return

def D():
	(n, k) = LI()
	a = S()
	ans = 0
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			ans += 1
	print(min(n - 1, ans + 2 * k))
	return

def E():

	def add(i):
		while i < len(bit):
			bit[i] += 1
			i += i & -i

	def sum(i):
		res = 0
		while i > 0:
			res += bit[i]
			i -= i & -i
		return res
	n = I()
	p = LI()
	p = [(p[i], i + 2) for i in range(n)]
	p.sort(key=lambda x: -x[0])
	bit = [0] * (n + 3)
	add(p[0][1])
	ans = 0
	for (pi, i) in p[1:]:
		s = sum(i)
		l = 0
		r = i
		while r - l > 1:
			m = l + r >> 1
			if sum(m) == s:
				r = m
			else:
				l = m
		x1 = r
		l = i
		r = n + 2
		while r - l > 1:
			m = l + r >> 1
			if sum(m) == s:
				l = m
			else:
				r = m
		x2 = r
		s_ = s - 1
		l = 0
		r = x1
		while r - l > 1:
			m = l + r >> 1
			if sum(m) == s_:
				r = m
			else:
				l = m
		x3 = r
		s_ = s + 1
		l = x2
		r = n + 2
		while r - l > 1:
			m = l + r >> 1
			if sum(m) == s_:
				l = m
			else:
				r = m
		x4 = r
		ans += pi * ((x1 - x3) * (x2 - i) + (x4 - x2) * (i - x1))
		add(i)
	print(ans)
	return

def F():
	n = I()
	s = LI()
	s.sort()
	s = s[::-1]
	m = 1 << n
	f = [-1] * m
	f[0] = 0
	for i in range(n):
		k = 0
		l = 0
		for j in range(1 << i):
			while f[k] != i:
				k += 1
			while f[l] >= i or s[k] <= s[l]:
				l += 1
				if l == m:
					print('No')
					return
			f[l] = i + 1
			k += 1
		for j in range(m):
			if f[j] >= 0:
				f[j] = i + 1
	print('Yes')
	return
E()


import bisect
N = int(input())
P = list(map(int, input().split()))
pos = [-1] * (N + 1)
for i in range(N):
	pos[P[i]] = i
called = [-1, -1, pos[N], N, N]
ans = 0
for i in range(N - 1, 0, -1):
	hoge = pos[i]
	r = bisect.bisect_left(called, hoge)
	R = called[r]
	RR = called[r + 1]
	L = called[r - 1]
	LL = called[r - 2]
	ans += i * ((RR - R) * (hoge - L) + (L - LL) * (R - hoge))
	called.insert(r, hoge)
print(ans)


N = int(input())
P = list(map(int, input().split()))
I = [0] * N
for i in range(N):
	I[P[i] - 1] = i
ans = 0
L = [i for i in range(-1, N - 1)]
R = [i for i in range(1, N + 1)]
for p in range(1, N + 1):
	i = I[p - 1]
	if R[i] < N:
		L[R[i]] = L[i]
	if L[i] >= 0:
		R[L[i]] = R[i]
	l1 = L[i]
	l2 = L[l1] if l1 >= 0 else -1
	r1 = R[i]
	r2 = R[r1] if r1 < N else N
	ans += p * ((r1 - i) * (l1 - l2) + (i - l1) * (r2 - r1))
print(ans)


N = int(input())
P = list(map(int, input().split()))
order = [None] * N
for (i, p) in enumerate(P):
	order[p - 1] = i
bit = [0] * (N + 2)

def bit_add(x, w):
	while x <= N + 1:
		bit[x] += w
		x += x & -x

def bit_sum(x):
	ret = 0
	while x > 0:
		ret += bit[x]
		x -= x & -x
	return ret

def bisect_right(k):

	def is_ok(i):
		if i < 1:
			return True
		if i > N + 1:
			return False
		return bit_sum(i) <= k
	ok = 0
	ng = N + 2
	while ng - ok > 1:
		m = (ok + ng) // 2
		if is_ok(m):
			ok = m
		else:
			ng = m
	return ok
ans = 0
for (q, i) in enumerate(reversed(order)):
	bit_add(i + 2, 1)
	k = bit_sum(i + 2)
	a = bisect_right(k - 3)
	b = bisect_right(k - 2)
	c = bisect_right(k - 1)
	d = bisect_right(k)
	e = bisect_right(k + 1)
	ans += ((b - a) * (d - c) + (c - b) * (e - d)) * (N - q)
print(ans)


import heapq
N = int(input())
P = list(map(int, input().split()))
Llis = []
Rlis = []
for i in range(N):
	Llis.append([N, N])
	Rlis.append([N, N])
	P[i] -= 1
LQ1 = []
LQ2 = []
for i in range(N):
	while len(LQ2) > 0 and LQ2[0][0] < P[i]:
		Llis[LQ2[0][1]][1] = i
		heapq.heappop(LQ2)
	while len(LQ1) > 0 and LQ1[0][0] < P[i]:
		Llis[LQ1[0][1]][0] = i
		heapq.heappush(LQ2, LQ1[0])
		heapq.heappop(LQ1)
	heapq.heappush(LQ1, [P[i], i])
P.reverse()
LQ1 = []
LQ2 = []
for i in range(N):
	while len(LQ2) > 0 and LQ2[0][0] < P[i]:
		Rlis[LQ2[0][1]][1] = i
		heapq.heappop(LQ2)
	while len(LQ1) > 0 and LQ1[0][0] < P[i]:
		Rlis[LQ1[0][1]][0] = i
		heapq.heappush(LQ2, LQ1[0])
		heapq.heappop(LQ1)
	heapq.heappush(LQ1, [P[i], i])
Rlis.reverse()
ans = 0
P.reverse()
for i in range(N):
	Llenge = Llis[i][1] - Llis[i][0]
	Rlenge = 1 + max(0, i - (N - Rlis[i][0]))
	ans += (P[i] + 1) * Llenge * Rlenge
P.reverse()
Rlis.reverse()
Llis.reverse()
for i in range(N):
	Rlenge = Rlis[i][1] - Rlis[i][0]
	Llenge = 1 + max(0, i - (N - Llis[i][0]))
	ans += (P[i] + 1) * Llenge * Rlenge
print(ans)


class SparseTable:

	def __init__(self, a, func=max, one=-10 ** 18):
		self.table = [a[:]]
		self.n = len(a)
		self.logn = self.n.bit_length()
		self.func = func
		self.one = one
		for i in map(lambda x: 1 << x, range(self.logn - 1)):
			self.table.append([])
			for j in range(self.n - i * 2 + 1):
				self.table[-1].append(self.func(self.table[-2][j], self.table[-2][j + i]))

	def get_section(self, i, j):
		length = j - i
		log = length.bit_length() - 1
		if length <= 0:
			return self.one
		a = self.func(self.table[log][i], self.table[log][j - (1 << log)])
		return a

def low(m, x):
	mi = 0
	ma = m - 1
	if ma < 0 or sp.get_section(0, m) <= x:
		return -1
	while mi != ma:
		mm = (mi + ma) // 2 + 1
		if sp.get_section(mm, m) > x:
			mi = mm
		else:
			ma = mm - 1
	return mi

def high(m, x):
	mi = m
	ma = n - 1
	if m >= n or sp.get_section(m, n) <= x:
		return n
	while mi != ma:
		mm = (mi + ma) // 2
		if sp.get_section(m, mm + 1) > x:
			ma = mm
		else:
			mi = mm + 1
	return mi
n = int(input())
p = [int(i) for i in input().split()]
sp = SparseTable(p)
ans = 0
for i in range(n):
	j = low(i, p[i])
	k = low(j, p[i])
	l = high(i, p[i])
	m = high(l + 1, p[i])
	ans += p[i] * ((i - j) * (m - l) + (j - k) * (l - i))
print(ans)


import math
import os
import sys
DEBUG = 'DEBUG' in os.environ

def inp():
	return sys.stdin.readline().rstrip()

def dprint(*value, sep=' ', end='\n'):
	if DEBUG:
		print(*value, sep=sep, end=end)

def solve(N, P):
	revp = [-1] * (N + 1)
	for (i, p) in enumerate(P):
		revp[p] = i
	segt = [[(v, 0) for v in P]]
	while len(segt[-1]) > 1:
		base = segt[-1]
		if len(base) % 2 == 1:
			base.append((0, 0))
		new = []
		for i in range(len(base) // 2):
			(a, b) = base[2 * i]
			(c, d) = base[2 * i + 1]
			arr = [a, b, c, d]
			arr.sort()
			new.append((arr[-1], arr[-2]))
		segt.append(new)
	dprint('segt', segt)

	def get12(i, j):
		if j - i <= 0:
			return (0, 0)
		segi = 0
		top = []
		while True:
			if j - i <= 0:
				break
			seg = segt[segi]
			if j - i == 1:
				top.extend(seg[i])
				break
			if i % 2 == 1:
				top.extend(seg[i])
				i += 1
			if j % 2 == 1:
				top.extend(seg[j - 1])
				j -= 1
			i //= 2
			j //= 2
			segi += 1
		top.sort()
		return (top[-1], top[-2])
	cache = [dict() for _ in range(N)]
	stk = [(0, N)]
	while stk:
		item = stk.pop()
		if len(item) == 2:
			(i, j) = item
			if j in cache[i]:
				continue
			(a, b) = get12(i, j)
			ai = revp[a]
			bi = revp[b]
			(li, ri) = (ai, bi) if ai < bi else (bi, ai)
			ri += 1
			sc = b * (li - i + 1) * (j - ri + 1)
			want = [(i, ri - 1), (li + 1, j), (li + 1, ri - 1)]
			req = []
			for (c, d) in want:
				if not (d - c < 2 or d in cache[c]):
					req.append((c, d))
			if not req:
				(left, right, mid) = [0 if d - c < 2 else cache[c][d] for (c, d) in want]
				cache[i][j] = left + right - mid + sc
				continue
			stk.append((i, j, want, sc))
			for r in req:
				stk.append(r)
			continue
		(i, j, want, sc) = item
		(left, right, mid) = [0 if d - c < 2 else cache[c][d] for (c, d) in want]
		cache[i][j] = left + right - mid + sc
	return cache[0][N]

def main():
	N = int(inp())
	P = [int(e) for e in inp().split()]
	print(solve(N, P))
main()


def binary_search(cond, left_initial, right_initial):
	left = left_initial
	right = right_initial
	while left + 1 < right:
		mid = (left + right) // 2
		if cond(mid):
			right = mid
		else:
			left = mid
	return left

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 solve_e(n, p_list):
	ind_list = [0] * (n + 1)
	for i in range(n):
		ind_list[p_list[i]] = i + 1
	bit = Bit(n + 1)
	res = 0
	for i in range(n, 0, -1):
		ind = ind_list[i]
		bit.add(ind, 1)
		r1 = n + 1
		r2 = n + 1
		if bit.sum(n + 1) - bit.sum(ind) > 0:
			r1 = binary_search(lambda k: bit.sum(k) - bit.sum(ind) >= 1, ind, n + 1) + 1
		if bit.sum(n + 1) - bit.sum(ind) > 1:
			r2 = binary_search(lambda k: bit.sum(k) - bit.sum(ind) >= 2, ind, n + 1) + 1
		l1 = 0
		l2 = 0
		if bit.sum(ind) >= 2:
			l1 = binary_search(lambda k: bit.sum(ind) - bit.sum(k) <= 1, 0, ind) + 1
		if bit.sum(ind) >= 3:
			l2 = binary_search(lambda k: bit.sum(ind) - bit.sum(k) <= 2, 0, ind) + 1
		cnt = (ind - l1) * (r2 - r1) + (l1 - l2) * (r1 - ind)
		res += cnt * i
	return res

def main():
	n = int(input())
	p_list = list(map(int, input().split()))
	print(solve_e(n, p_list))
main()


class SegmentTree:

	def __init__(self, A, dot, e):
		n = 2 ** (len(A) - 1).bit_length()
		self.__n = n
		self.__dot = dot
		self.__e = e
		self.__node = [e] * (2 * n)

	def update(self, i, c):
		i += self.__n
		node = self.__node
		node[i] = c
		while i > 0:
			i //= 2
			node[i] = self.__dot(node[2 * i], node[2 * i + 1])

	def get(self, l, r):
		(vl, vr) = (self.__e, self.__e)
		l += self.__n
		r += self.__n
		while l < r:
			if l & 1:
				vl = self.__dot(vl, self.__node[l])
				l += 1
			l //= 2
			if r & 1:
				r -= 1
				vr = self.__dot(vr, self.__node[r])
			r //= 2
		return self.__dot(vl, vr)

def solve():
	N = int(input())
	P = map(int, input().split())
	plist = []
	for (i, p) in enumerate(P):
		plist.append((p, i))
	plist.sort(reverse=True)
	maxSeg = SegmentTree([-1] * N, max, -1)
	minSeg = SegmentTree([N] * N, min, N)
	cnt = 0
	for (p, c) in plist:
		l2 = maxSeg.get(0, c)
		l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)
		r1 = minSeg.get(c + 1, N)
		r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)
		a = (l2 - l1) * (r1 - c)
		b = (r2 - r1) * (c - l2)
		cnt += p * (a + b)
		maxSeg.update(c, c)
		minSeg.update(c, c)
	print(cnt)
solve()


class BIT1:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (self.n + 1)
		self.data = [0] * (self.n + 1)

	def build(self, data):
		pass

	def add(self, idx, x):
		self.data[idx] += x
		while idx <= self.n:
			self.bit[idx] += x
			idx += idx & -idx

	def sum(self, idx):
		s = 0
		while idx:
			s += self.bit[idx]
			idx -= idx & -idx
		return s

	def bisect_left(self, w):
		if w <= 0:
			return 0
		idx = 0
		k = 1 << self.n.bit_length() - 1
		while k > 0:
			if idx + k <= self.n and self.bit[idx + k] < w:
				w -= self.bit[idx + k]
				idx += k
			k = k >> 1
		return idx + 1

	def bisect_right(self, w):
		if w < 0:
			return 0
		idx = 0
		k = 1 << self.n.bit_length() - 1
		while k > 0:
			if idx + k <= self.n and self.bit[idx + k] <= w:
				w -= self.bit[idx + k]
				idx += k
			k = k >> 1
		return idx + 1
n = int(input())
p = [0] + list(map(int, input().split()))
p2idx = [0] * (n + 1)
for i in range(1, n + 1):
	p2idx[p[i]] = i
ans = 0
bit = BIT1(n)
for x in reversed(range(1, n + 1)):
	idx = p2idx[x]
	bit.add(idx, 1)
	idx_rank = bit.sum(idx)
	idx_l2 = bit.bisect_left(idx_rank - 2)
	idx_l1 = bit.bisect_left(idx_rank - 1)
	idx_r1 = bit.bisect_left(idx_rank + 1)
	idx_r2 = bit.bisect_left(idx_rank + 2)
	cnt = 0
	cnt += (idx_l1 - idx_l2) * (idx_r1 - idx)
	cnt += (idx - idx_l1) * (idx_r2 - idx_r1)
	ans += x * cnt
print(ans)


class BIT:

	def __init__(self, n, init_list):
		self.num = n + 1
		self.tree = [0] * self.num
		for (i, e) in enumerate(init_list):
			self.update(i, e)

	def update(self, k, x):
		k = k + 1
		while k < self.num:
			self.tree[k] += x
			k += k & -k
		return

	def query(self, l, r):
		ret = 0
		while r > 0:
			ret += self.tree[r]
			r -= r & -r
		while l > 0:
			ret -= self.tree[l]
			l -= l & -l
		return ret
N = int(input())
A = list(map(int, input().split()))
idxlist = [0] * N
for (i, a) in enumerate(A):
	idxlist[a - 1] = i + 2
A = [N + 1] * 2 + A + [N + 1] * 2
ans = 0
seg = BIT(N + 4, [1] * 2 + [0] * N + [1] * 2)

def judge(l, r, key):
	if l > r:
		(l, r) = (r, l)
	res = seg.query(l, r + 1)
	if res > key:
		return False
	else:
		return True

def bsearch(idx, ng, key):
	ok = idx
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		if judge(idx, mid, key):
			ok = mid
		else:
			ng = mid
	return ng
for idx in reversed(idxlist):
	if A[idx] == N:
		seg.update(idx, 1)
		continue
	ng_l = 0
	ng_r = N + 3
	L1 = bsearch(idx, ng_l, 0)
	L2 = bsearch(idx, ng_l, 1)
	R1 = bsearch(idx, ng_r, 0)
	R2 = bsearch(idx, ng_r, 1)
	coef = 0
	if A[L1] != N + 1:
		coef += (L1 - L2) * (R1 - idx)
	if A[R1] != N + 1:
		coef += (R2 - R1) * (idx - L1)
	ans += A[idx] * coef
	seg.update(idx, 1)
print(ans)


class MinSegmentTree:

	def __init__(self, n):
		self.n = n
		self.INF = n - 1
		self.size = 1
		while self.size < n:
			self.size *= 2
		self.node = [self.INF] * (2 * self.size - 1)

	def update(self, i, val):
		i += self.size - 1
		self.node[i] = val
		while i > 0:
			i = (i - 1) // 2
			self.node[i] = min(self.node[2 * i + 1], self.node[2 * i + 2])

	def get_min(self, begin, end):
		begin += self.size - 1
		end += self.size - 1
		s = self.INF
		while begin < end:
			if end - 1 & 1:
				end -= 1
				s = min(s, self.node[end])
			if begin - 1 & 1:
				s = min(s, self.node[begin])
				begin += 1
			begin = (begin - 1) // 2
			end = (end - 1) // 2
		return s

class MaxSegmentTree:

	def __init__(self, n):
		self.n = n
		self.INF = 0
		self.size = 1
		while self.size < n:
			self.size *= 2
		self.node = [self.INF] * (2 * self.size - 1)

	def update(self, i, val):
		i += self.size - 1
		self.node[i] = val
		while i > 0:
			i = (i - 1) // 2
			self.node[i] = max(self.node[2 * i + 1], self.node[2 * i + 2])

	def get_max(self, begin, end):
		begin += self.size - 1
		end += self.size - 1
		s = self.INF
		while begin < end:
			if end - 1 & 1:
				end -= 1
				s = max(s, self.node[end])
			if begin - 1 & 1:
				s = max(s, self.node[begin])
				begin += 1
			begin = (begin - 1) // 2
			end = (end - 1) // 2
		return s
n = int(input())
a = list(map(int, input().split()))
ind = {}
for i in range(n):
	ind[a[i]] = i
smax = MaxSegmentTree(n + 2)
smin = MinSegmentTree(n + 2)
ans = 0
for i in range(n):
	pos = ind[n - i] + 1
	l2 = smax.get_max(0, pos)
	l1 = smax.get_max(0, l2)
	r1 = smin.get_min(pos + 1, n + 2)
	r2 = smin.get_min(r1 + 1, n + 2)
	smin.update(pos, pos)
	smax.update(pos, pos)
	ans += ((l2 - l1) * (r1 - pos) + (r2 - r1) * (pos - l2)) * (n - i)
print(ans)


n = int(input())
p = list(map(int, input().split()))

def get_de(p):
	(d, e) = ([n for i in range(n)], [n for i in range(n)])
	stack1 = []
	stack2 = []
	for i in range(n):
		while stack2 and p[stack2[-1]] < p[i]:
			idx = stack2.pop()
			e[idx] = i
		to_append = []
		while stack1 and p[stack1[-1]] < p[i]:
			idx = stack1.pop()
			d[idx] = i
			to_append.append(idx)
		while to_append:
			stack2.append(to_append.pop())
		stack1.append(i)
	(dist1, dist2) = ([], [])
	for i in range(n):
		dist1.append(d[i] - i)
		dist2.append(e[i] - d[i])
	return (dist1, dist2)
(dist1, dist2) = get_de(p)
(dist3, dist4) = get_de(p[::-1])
(dist3, dist4) = (dist3[::-1], dist4[::-1])
ans = 0
for i in range(n):
	ans += (dist1[i] * dist4[i] + dist2[i] * dist3[i]) * p[i]
print(ans)


from bisect import bisect_left, bisect_right, insort_right

class SquareSkipList:

	def __init__(self, values=None, sorted_=False, square=1000, seed=42):
		inf = float('inf')
		self.rand_y = seed
		self.square = square
		if values is None:
			self.layer1 = []
			self.layer0 = [[]]
		else:
			self.layer1 = layer1 = []
			self.layer0 = layer0 = []
			if not sorted_:
				values.sort()
			rand_depth = self.rand_depth
			l0 = []
			for v in values:
				if rand_depth():
					layer0.append(l0)
					l0 = []
					layer1.append(v)
				else:
					l0.append(v)
			layer0.append(l0)
		self.layer1.append(inf)

	def rand_depth(self):
		y = self.rand_y
		y ^= y << 13 & 4294967295
		y ^= y >> 17
		y ^= y << 5 & 4294967295
		self.rand_y = y
		return y % self.square == 0

	def add(self, x):
		(layer1, layer0) = (self.layer1, self.layer0)
		if self.rand_depth():
			idx1 = bisect_right(layer1, x)
			layer1.insert(idx1, x)
			layer0_idx1 = layer0[idx1]
			idx0 = bisect_right(layer0_idx1, x)
			layer0.insert(idx1 + 1, layer0_idx1[idx0:])
			del layer0_idx1[idx0:]
		else:
			idx1 = bisect_right(layer1, x)
			insort_right(layer0[idx1], x)

	def remove(self, x):
		(layer1, layer0) = (self.layer1, self.layer0)
		idx1 = bisect_left(layer1, x)
		if layer1[idx1] == x:
			del layer1[idx1]
			layer0[idx1] += layer0[idx1 + 1]
			del layer0[idx1 + 1]
		else:
			layer0_idx1 = layer0[idx1]
			del layer0_idx1[bisect_left(layer0_idx1, x)]

	def bisect_left(self, x):
		(layer1, layer0) = (self.layer1, self.layer0)
		idx1 = bisect_left(layer1, x)
		res = layer1[idx1]
		if res == x:
			return res
		layer0_idx1 = layer0[idx1]
		if layer0_idx1:
			idx0 = bisect_left(layer0_idx1, x)
			if idx0 == len(layer0_idx1):
				return res
			else:
				return layer0_idx1[idx0]
		else:
			return res

	def search_higher(self, x):
		(layer1, layer0) = (self.layer1, self.layer0)
		idx1 = bisect_right(layer1, x)
		res = layer1[idx1]
		layer0_idx1 = layer0[idx1]
		if layer0_idx1:
			idx0 = bisect_right(layer0_idx1, x)
			if idx0 == len(layer0_idx1):
				return res
			else:
				return layer0_idx1[idx0]
		else:
			return res

	def search_lower(self, x):
		(layer1, layer0) = (self.layer1, self.layer0)
		idx1 = bisect_left(layer1, x)
		res = layer1[idx1]
		layer0_idx1 = layer0[idx1]
		if res != x:
			if layer0_idx1:
				idx0 = bisect_left(layer0_idx1, x)
				if idx0 != 0:
					return layer0_idx1[idx0 - 1]
			return layer1[idx1 - 1]
		else:
			idx0 = bisect_left(layer0_idx1, x)
			if idx0 == 0:
				return layer1[idx1 - 1]
			else:
				return layer0_idx1[idx0 - 1]

	def pop(self, idx):
		(layer1, layer0) = (self.layer1, self.layer0)
		s = -1
		for (i, l0) in enumerate(layer0):
			s += len(l0) + 1
			if s >= idx:
				break
		if s == idx:
			layer0[i] += layer0[i + 1]
			del layer0[i + 1]
			return layer1.pop(i)
		else:
			return layer0[i].pop(idx - s)
N = int(input())
P = list(map(int, input().split()))
D = {P[i]: i + 1 for i in range(N)}
ans = 0
L = SquareSkipList()
L.add(D[N])
for i in range(1, N)[::-1]:
	l = L.search_lower(D[i])
	h = L.search_higher(D[i])
	if l == float('inf'):
		hh = L.search_higher(h)
		if hh == float('inf'):
			hh = N + 1
		ans += D[i] * (hh - h) * i
	elif h == float('inf'):
		ll = L.search_lower(l)
		if ll == float('inf'):
			ll = 0
		ans += (N + 1 - D[i]) * (l - ll) * i
	else:
		hh = L.search_higher(h)
		if hh == float('inf'):
			hh = N + 1
		ll = L.search_lower(l)
		if ll == float('inf'):
			ll = 0
		ans += ((h - D[i]) * (l - ll) + (D[i] - l) * (hh - h)) * i
	L.add(D[i])
print(ans)


import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0] * (N + 1)
for i in range(N):
	P_id[P[i]] = i
A = array.array('i', [-1, P_id[N], N])
res = 0
for i in range(N - 1, 0, -1):
	j = bisect.bisect_left(A, P_id[i])
	A.insert(j, P_id[i])
	l1 = A[j - 1]
	r1 = A[j + 1]
	l2 = l1
	r2 = r1
	if l1 != -1:
		l2 = A[j - 2]
	if r1 != N:
		r2 = A[j + 2]
	res += i * ((A[j] - l1) * (r2 - r1) + (l1 - l2) * (r1 - A[j]))
print(res)


n = int(input())
P = list(map(int, input().split()))
num_idx = [0] * (n + 1)
right_idx_over_current_pos = list(range(1, n + 1)) + [n, n]
left_idx_over_current_pos = list(range(-1, n - 1)) + [-1, -1]
for (idx, num) in enumerate(P):
	num_idx[num] = idx
ans = 0
for num in range(1, n + 1):
	now = num_idx[num]
	r1 = right_idx_over_current_pos[now]
	r2 = right_idx_over_current_pos[r1]
	l1 = left_idx_over_current_pos[now]
	l2 = left_idx_over_current_pos[l1]
	r_pattern = (r2 - r1) * (now - l1)
	l_pattern = (l1 - l2) * (r1 - now)
	right_idx_over_current_pos[l1] = r1
	left_idx_over_current_pos[r1] = l1
	ans += (r_pattern + l_pattern) * num
print(ans)


class SearchableBIT:

	def __init__(self, size):
		self.size = size
		self.data = [0] * (size + 1)
		self.cnt = 0

	def add(self, a):
		x = a
		self.cnt += 1
		while x <= self.size:
			self.data[x] += 1
			x += x & -x

	def delete(self, x):
		self.cnt -= 1
		while x <= self.size:
			self.data[x] -= 1
			x += x & -x

	def count(self, x):
		ret = 0
		while x > 0:
			ret += self.data[x]
			x -= x & -x
		return ret

	def get_lower_i(self, i):
		ng = -1
		ok = self.size + 1
		while ok - ng > 1:
			mid = (ok + ng) // 2
			if self.count(mid) >= i:
				ok = mid
			else:
				ng = mid
		return ok
n = int(input())
P = list(map(int, input().split()))
Idx = [0] * (n + 1)
for (i, p) in enumerate(P):
	Idx[p] = i + 1
BIT = SearchableBIT(n)
ans = 0
for i in reversed(range(1, n + 1)):
	idx = Idx[i]
	BIT.add(idx)
	cnt = BIT.count(idx)
	l_idx1 = BIT.get_lower_i(cnt - 1)
	l_idx2 = BIT.get_lower_i(cnt - 2)
	r_idx1 = BIT.get_lower_i(cnt + 1)
	r_idx2 = BIT.get_lower_i(cnt + 2)
	l1 = idx - l_idx1
	l2 = l_idx1 - l_idx2
	r1 = r_idx1 - idx
	r2 = r_idx2 - r_idx1
	if r_idx1 != n + 1:
		ans += i * l1 * r2
	if l_idx1 != 0:
		ans += i * l2 * r1
print(ans)


N = int(input())
P = [int(x) for x in input().split()]
PIdx = sorted([(i + 1, v) for (i, v) in enumerate(P)], key=lambda x: x[1])
L = [0]
for i in range(N + 1):
	L.append(i)
R = [i + 1 for i in range(N + 1)]
R.append(N + 1)
ans = 0
for (i, v) in PIdx:
	l1 = L[i]
	l2 = L[l1]
	r1 = R[i]
	r2 = R[r1]
	ans += v * ((i - l1) * (r2 - r1) + (l1 - l2) * (r1 - i))
	L[r1] = l1
	R[l1] = r1
print(ans)


def f_e():
	(n, *p) = list(map(int, open(0).read().split()))
	p = sorted([(v, i) for (i, v) in enumerate(p)])
	(*l,) = list(range(-1, n - 1))
	(*r,) = list(range(1, n + 1))
	a = 0
	for (v, i) in p:
		(l0, r0) = (l[i], r[i])
		l1 = l[l0] if l0 > -1 else l0
		r1 = r[r0] if r0 < n else r0
		a += ((l0 - l1) * (r0 - i) + (r1 - r0) * (i - l0)) * v
		if l0 > -1:
			r[l0] = r0
		if r0 < n:
			l[r0] = l0
	print(a)

def __starting_point():
	f_e()
__starting_point()


import bisect

def find_left(P, position):
	N = len(P)
	left1 = [-1] * N
	left2 = [-1] * N
	stack = []
	popped = [[] for i in range(len(P))]
	stack = [P[0]]
	for i in range(1, len(P)):
		while stack:
			if stack[-1] < P[i]:
				popped[i] += [stack.pop()]
			else:
				left1[i] = stack[-1]
				stack += [P[i]]
				break
		if stack == []:
			stack += [P[i]]
			left1[i] = -1
		if left1[i] == -1:
			left2[i] == -1
		else:
			val = left1[i]
			pos = position[val]
			big_val_pos = len(popped[pos])
			if popped[pos]:
				big_val_pos = bisect.bisect_left(popped[pos], P[i])
				if big_val_pos < len(popped[pos]):
					left2[i] = popped[pos][big_val_pos]
			if left2[i] == -1:
				if len(stack) >= 3:
					left2[i] = stack[-3]
	return (left1, left2)

def find_right(P, position):
	position = [len(P) - x - 1 for x in position]
	(right1, right2) = find_left(P[::-1], position)
	return (right1[::-1], right2[::-1])
input()
P = list(map(int, input().strip().split(' ')))
N = len(P)
P = [p - 1 for p in P]
position = [0] * len(P)
for i in range(len(P)):
	position[P[i]] = i
(left1, left2) = find_left(P, position)
(right1, right2) = find_right(P, position)
for i in range(N):
	if left1[i] != -1:
		left1[i] = position[left1[i]]
	if left2[i] != -1:
		left2[i] = position[left2[i]]
	if right1[i] == -1:
		right1[i] = N
	else:
		right1[i] = position[right1[i]]
	if right2[i] == -1:
		right2[i] = N
	else:
		right2[i] = position[right2[i]]
ans = 0
for i in range(N):
	(L1, L2, R1, R2) = (left1[i], left2[i], right1[i], right2[i])
	val = P[i] + 1
	if val == N:
		continue
	temp = 0
	if L1 == -1:
		temp += (i + 1) * (R2 - R1)
	elif R1 == N:
		temp += (L1 - L2) * (N - i)
	else:
		temp += (L1 - L2) * (R1 - i)
		temp += (i - L1) * (R2 - R1)
	ans += temp * val
print(ans)


N = int(input())
P = [int(x) for x in input().split()]
L = [0] * (N + 2)
R = [N + 1] * (N + 2)
I = list(range(N + 1))
for i in range(N):
	I[P[i]] = i
ans = 0
ST = [0] * (N + 2)

def cnt(i):
	ret = 0
	while i:
		ret += ST[i]
		i -= i & -i
	return ret

def update(i):
	while i <= N + 1:
		ST[i] += 1
		i += i & -i

def ls(idx):
	b = cnt(idx)
	if b == 0:
		return 0
	s = 0
	t = idx
	while t - s > 1:
		m = (s + t) // 2
		if cnt(m) < b:
			s = m
		else:
			t = m
	return t

def rs(idx):
	b = cnt(idx)
	s = idx
	t = N + 1
	while t - s > 1:
		m = (s + t) // 2
		if cnt(m) > b:
			t = m
		else:
			s = m
	return t
for i in range(N, 0, -1):
	index = I[i]
	idx = index + 1
	L[idx] = ls(idx)
	R[idx] = rs(idx)
	L[R[idx]] = idx
	R[L[idx]] = idx
	update(idx)
	ans += i * ((idx - L[idx]) * (R[R[idx]] - R[idx]) + (L[idx] - L[L[idx]]) * (R[idx] - idx))
print(ans)


from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque

def main():
	num = int(input())
	data = list(map(int, input().split()))
	for i in range(num):
		data[i] = (data[i], i + 1)
	data.sort(key=lambda x: x[0])
	left = [0, 0] + [i + 1 for i in range(num)]
	right = [i + 1 for i in range(num)] + [num + 1, num + 1]
	ans = 0
	for i in range(num):
		(ori_num, ori_ind) = data[i]
		l1 = left[ori_ind]
		l2 = left[l1]
		r1 = right[ori_ind]
		r2 = right[r1]
		ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num
		right[l1] = r1
		left[r1] = l1
	print(ans)
main()


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
n = I()
p = LI()
f = [0] * (n + 1)
for i in range(n):
	f[p[i]] = i + 1
ans = 0
l = [0] + [i for i in range(n + 1)]
r = [i + 1 for i in range(n + 1)] + [n + 1]
for i in range(1, n + 1):
	x = f[i]
	(l1, r1) = (l[x], r[x])
	(l2, r2) = (l[l1], r[r1])
	ans += ((l1 - l2) * (r1 - x) + (x - l1) * (r2 - r1)) * i
	(l[r1], r[l1]) = (l1, r1)
print(ans)


N = int(input())
(*P,) = map(int, input().split())
N += 1
data = [0] * (N + 1)

def add(k, x):
	while k <= N:
		data[k] += x
		k += k & -k

def get(k):
	s = 0
	while k:
		s += data[k]
		k -= k & -k
	return s
N0 = 2 ** (N - 1).bit_length()

def lower_bound(x):
	w = i = 0
	k = N0
	while k:
		if i + k <= N and w + data[i + k] <= x:
			w += data[i + k]
			i += k
		k >>= 1
	return i + 1
E = [(v, i) for (i, v) in enumerate(P)]
E.sort(reverse=1)
add(1, 1)
add(N + 1, 1)
ans = 0
for (v, i) in E:
	k = get(i + 2)
	l1 = lower_bound(k - 2)
	l0 = lower_bound(k - 1)
	r0 = lower_bound(k)
	r1 = lower_bound(k + 1)
	if l0 > 1:
		ans += (l0 - l1) * (r0 - (i + 2)) * v
	if r0 < N + 2:
		ans += (r1 - r0) * (i + 2 - l0) * v
	add(i + 2, 1)
print(ans)


def main():

	class unionfind:

		def __init__(self, size):
			self.size = size
			self.tree = [i for i in range(self.size)]

		def root(self, index):
			temp_list = []
			temp = self.tree[index]
			while index != temp:
				temp_list.append(index)
				index = temp
				temp = self.tree[index]
			for i in temp_list:
				self.tree[i] = index
			return index

		def unite_r(self, index1, index2):
			r1 = self.root(index1)
			r2 = self.root(index2)
			if r1 < r2:
				self.tree[r1] = r2
			else:
				self.tree[r2] = r1

		def unite_l(self, index1, index2):
			r1 = self.root(index1)
			r2 = self.root(index2)
			if r1 > r2:
				self.tree[r1] = r2
			else:
				self.tree[r2] = r1

		def same(self, index1, index2):
			r1 = self.root(index1)
			r2 = self.root(index2)
			return r1 == r2
	n = int(input())
	a = list(map(int, input().split()))
	d = [0] * n
	for (i, j) in enumerate(a):
		d[j - 1] = i + 2
	vis = [False] * (n + 4)
	u_r = unionfind(n + 4)
	u_l = unionfind(n + 4)
	ans = 0
	for (j, i) in enumerate(d[:-1]):
		vis[i] = True
		if vis[i + 1] == True:
			u_r.unite_r(i, i + 1)
			u_l.unite_l(i, i + 1)
			k1 = u_r.root(i + 1) + 1
		else:
			k1 = i + 1
		if vis[k1 + 1] == True:
			cnt1 = u_r.root(k1 + 1) + 1
		else:
			cnt1 = k1 + 1
		cnt1 = min(cnt1, n + 2)
		if vis[i - 1] == True:
			u_r.unite_r(i, i - 1)
			u_l.unite_l(i, i - 1)
			k2 = u_l.root(i - 1) - 1
		else:
			k2 = i - 1
		if vis[k2 - 1] == True:
			cnt2 = u_l.root(k2 - 1) - 1
		else:
			cnt2 = k2 - 1
		cnt2 = max(cnt2, 1)
		ans += ((k2 - cnt2) * (k1 - i) + (cnt1 - k1) * (i - k2)) * (j + 1)
	print(ans)
main()


from sys import setrecursionlimit as SRL, stdin
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
n = int(input())
p = list(rrd())
bit = [0] * 100005

def add(x):
	while x <= n:
		bit[x] += 1
		x += x & -x

def sum(x):
	tot = 0
	while x:
		tot += bit[x]
		x -= x & -x
	return tot

def search(x):
	tot = 0
	if x < 0:
		return tot
	for i in range(20)[::-1]:
		if (1 << i) + tot <= n and bit[(1 << i) + tot] <= x:
			tot += 1 << i
			x -= bit[tot]
	return tot + 1
idx = [0] * 100005
for i in range(n):
	idx[p[i]] = i + 1
ans = 0
for i in range(n, 0, -1):
	j = sum(idx[i])
	l1 = search(j - 1)
	l2 = search(j - 2)
	r1 = search(j)
	r2 = search(j + 1)
	tt = (idx[i] - l1) * (r2 - r1) + (r1 - idx[i]) * (l1 - l2)
	ans += tt * i
	add(idx[i])
print(ans)


from bisect import bisect, insort
N = int(input())
P = list(map(int, input().split()))
ind = [-1] * (N + 1)
for i in range(N):
	ind[P[i]] = i
doneind = [-2, -1, ind[N], N, N + 1]
ans = 0
for i in range(N - 1, 0, -1):
	j = bisect(doneind, ind[i])
	if doneind[j] != N:
		ans += i * (doneind[j + 1] - doneind[j]) * (ind[i] - doneind[j - 1])
	if doneind[j - 1] != -1:
		ans += i * (doneind[j] - ind[i]) * (doneind[j - 1] - doneind[j - 2])
	insort(doneind, ind[i])
print(ans)


import sys
INF = float('inf')

class MaxBit:

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

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

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

class MinBit:

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

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

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

def solve(N: int, P: 'List[int]'):
	prev = MaxBit(N + 2)
	foll = MinBit(N + 2)
	seq = [0] * (N + 2)
	inv = {p: i for (i, p) in enumerate(P)}
	ans = 0
	for i in range(N, 0, -1):
		prev.add(inv[i] + 2, inv[i] + 1)
		foll.add(N - inv[i] + 1, inv[i] + 1)
		seq[inv[i] + 1] = i
		p = prev.sum(inv[i] + 1)
		pp = prev.sum(p)
		f = foll.sum(N - inv[i])
		ff = foll.sum(N - f + 1)
		if p > 0:
			ans += i * (p - pp) * (f - (inv[i] + 1))
		if f < N + 1:
			ans += i * (inv[i] + 1 - p) * (ff - f)
	print(ans)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	P = [int(next(tokens)) for _ in range(N)]
	solve(N, P)
main()


n = int(input())
p = [int(i) for i in input().split()]
pos_list = [0] * n
for (ind, i) in enumerate(p):
	pos_list[i - 1] = ind
left_nextInd = list(range(-1, n - 1)) + [-1, -1]
right_nextInd = list(range(1, n + 1)) + [n, n]
answer = 0
for i in range(1, n):
	ind = pos_list[i - 1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]
	answer += i * ((ind - l1) * (r2 - r1) + (r1 - ind) * (l1 - l2))
	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)


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

class BIT:
	ini = 0

	def __init__(s, num):
		s.N = 1
		while s.N <= num:
			s.N *= 2
		s.T = [s.ini] * s.N

	def set(s, L):
		for i in range(len(L)):
			s.update(i, L[i])

	def update(s, x, v):
		k = x + 1
		s.T[k - 1] = max(s.T[k - 1], v)
		k += k & -k
		while k <= s.N:
			s.T[k - 1] = max(s.T[k - 1], v)
			k += k & -k

	def getV(s, x):
		if x <= 0:
			return 0
		ans = s.T[x - 1]
		x -= x & -x
		while x != 0:
			ans = max(ans, s.T[x - 1])
			x -= x & -x
		return ans

class segMin:
	inf = N + 1

	def __init__(s, num):
		s.N = 1
		while s.N < num:
			s.N *= 2
		s.T = [s.inf] * (2 * s.N - 1)

	def do(s, l, r):
		return min(l, r)

	def set(s, L):
		for i in range(len(L)):
			s.update(i, L[i])

	def update(s, x, v):
		k = x + s.N - 1
		s.T[k] = v
		while k > 0:
			k = (k - 1) // 2
			s.T[k] = s.do(s.T[2 * k + 1], s.T[2 * k + 2])

	def getV(s, l, r):
		if l > r:
			return s.inf
		return s.getVs(l, r, 0, 0, s.N - 1)

	def getVs(s, l, r, k, kl, kr):
		if l <= kl and r >= kr:
			return s.T[k]
		t = (kl + kr) // 2
		if l > t:
			return s.getVs(l, r, 2 * k + 2, t + 1, kr)
		if r < t + 1:
			return s.getVs(l, r, 2 * k + 1, kl, t)
		return s.do(s.getVs(l, r, 2 * k + 1, kl, t), s.getVs(l, r, 2 * k + 2, t + 1, kr))
ans = 0
D = [0] * (N + 1)
for i in range(N):
	D[P[i]] = i + 1
TMa = BIT(N + 1)
TMi = segMin(N + 1)
for i in range(N, 0, -1):
	t = D[i]
	ma = TMa.getV(t)
	ma2 = TMa.getV(ma)
	mi = TMi.getV(t, N + 1)
	mi2 = TMi.getV(mi + 1, N + 1)
	TMa.update(t, t)
	TMi.update(t, t)
	ans += (mi - t) * (ma - ma2) * i
	ans += (mi2 - mi) * (t - ma) * i
print(ans)


class SegmentTree:

	def __init__(self, iterable, func, e):
		self.func = func
		self.e = e
		ls = list(iterable)
		self.n = 1 << len(ls).bit_length()
		ls.extend([self.e] * (self.n - len(ls)))
		self.data = [self.e] * self.n + ls
		for i in range(self.n - 1, 0, -1):
			self.data[i] = self.func(self.data[2 * i], self.data[2 * i + 1])

	def replace(self, index, value):
		index += self.n
		self.data[index] = value
		index //= 2
		while index > 0:
			self.data[index] = self.func(self.data[2 * index], self.data[2 * index + 1])
			index //= 2

	def folded(self, l, r):
		left_folded = self.e
		right_folded = self.e
		l += self.n
		r += self.n
		while l < r:
			if l % 2:
				left_folded = self.func(left_folded, self.data[l])
				l += 1
			if r % 2:
				r -= 1
				right_folded = self.func(self.data[r], right_folded)
			l //= 2
			r //= 2
		return self.func(left_folded, right_folded)
N = int(input())
Ps = list(map(lambda c: int(c) - 1, input().split()))

def max_tuple(t1, t2):
	if t1[0] < t2[0]:
		(t1, t2) = (t2, t1)
	if t1[1] > t2[0]:
		return t1
	else:
		return (t1[0], t2[0])
max_two_elems = SegmentTree([(P, -1) for P in Ps], max_tuple, (-1, -1))
ans = 0
for (i, P) in enumerate(Ps):
	ok = 0
	ng = i + 1
	while ng - ok > 1:
		mid = (ng + ok) // 2
		(largest, _) = max_two_elems.folded(i - mid, i + 1)
		if largest == P:
			ok = mid
		else:
			ng = mid
	l_width_1 = ng
	if l_width_1 == i + 1:
		l_width_2 = 0
	else:
		ok = 0
		ng = i - l_width_1 + 1
		while ng - ok > 1:
			mid = (ng + ok) // 2
			(_, second_largest) = max_two_elems.folded(i - l_width_1 - mid, i + 1)
			if second_largest <= P:
				ok = mid
			else:
				ng = mid
		l_width_2 = ng
	ok = 0
	ng = N - i
	while ng - ok > 1:
		mid = (ng + ok) // 2
		(largest, _) = max_two_elems.folded(i, i + mid + 1)
		if largest == P:
			ok = mid
		else:
			ng = mid
	r_width_1 = ng
	if r_width_1 == N - i:
		r_width_2 = 0
	else:
		ok = 0
		ng = N - i - r_width_1
		while ng - ok > 1:
			mid = (ng + ok) // 2
			(_, second_largest) = max_two_elems.folded(i, i + r_width_1 + mid + 1)
			if second_largest <= P:
				ok = mid
			else:
				ng = mid
		r_width_2 = ng
	ans += (l_width_2 * r_width_1 + l_width_1 * r_width_2) * (P + 1)
print(ans)


from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_str():
	return list(sys.stdin.readline().split())

class Searchable_BIT:

	def __init__(self, N):
		self.N = N
		self.node = [0] * (self.N + 1)
		self.cnt = 0

	def add(self, a):
		x = a
		self.cnt += 1
		while x <= self.N:
			self.node[x] += 1
			x += x & -x

	def delete(self, x):
		self.cnt -= 1
		while x <= self.N:
			self.node[x] -= 1
			x += x & -x

	def count(self, x):
		tmp = 0
		while x > 0:
			tmp += self.node[x]
			x -= x & -x
		return tmp

	def get_maxval(self):
		return self.get_lower_i(self.cnt)

	def get_lower_i(self, i):
		NG = -1
		OK = self.N + 1
		while OK - NG > 1:
			mid = (OK + NG) // 2
			if self.count(mid) >= i:
				OK = mid
			else:
				NG = mid
		return OK
N = inp()
PP = inpl()
inds = [0] * (N + 1)
for (i, P) in enumerate(PP):
	inds[P] = i + 1
BIT = Searchable_BIT(N)
ans = 0
for i in reversed(range(1, N + 1)):
	ind = inds[i]
	BIT.add(ind)
	cnt = BIT.count(ind)
	Lind1 = BIT.get_lower_i(cnt - 1)
	Lind2 = BIT.get_lower_i(cnt - 2)
	Rind1 = BIT.get_lower_i(cnt + 1)
	Rind2 = BIT.get_lower_i(cnt + 2)
	L1 = ind - Lind1
	L2 = Lind1 - Lind2
	R1 = Rind1 - ind
	R2 = Rind2 - Rind1
	if Rind1 != N + 1:
		ans += i * L1 * R2
	if Lind1 != 0:
		ans += i * L2 * R1
print(ans)


N = int(input())
P = list(map(int, input().split()))
D = [0] * N
for i in range(N):
	D[P[i] - 1] = i

class BIT:

	def __init__(self, L):
		self.N = len(L)
		self.bit = [0] * self.N
		for (i, l) in enumerate(L):
			self.add(i, l)
		self.N0 = 1
		while self.N0 * 2 <= self.N:
			self.N0 *= 2

	def add(self, a, w):
		x = a + 1
		for i in range(1000):
			self.bit[x - 1] += w
			x += x & -x
			if x > self.N:
				break

	def sum(self, a):
		x = a + 1
		ret = 0
		for i in range(1000):
			ret += self.bit[x - 1]
			x -= x & -x
			if x <= 0:
				break
		return ret

	def lower_bound(self, w):
		if w <= 0:
			return 0
		x = 0
		k = self.N0
		while k > 0:
			if x + k <= self.N:
				if self.bit[x + k - 1] < w:
					w -= self.bit[x + k - 1]
					x += k
			k //= 2
		return x
bit = BIT([0] * N)

def calc_num(x, l1, l2, h1, h2):
	A = (l1 - l2) * (h1 - x)
	B = (h2 - h1) * (x - l1)
	return A + B
ans = 0
for i in range(N):
	j = N - i - 1
	bit.add(D[j], 1)
	s = bit.sum(D[j])
	if s == i + 1:
		h1 = h2 = N
	elif s == i:
		h2 = N
		h1 = bit.lower_bound(s + 1)
	else:
		h1 = bit.lower_bound(s + 1)
		h2 = bit.lower_bound(s + 2)
	if s == 1:
		l1 = l2 = -1
	elif s == 2:
		l1 = bit.lower_bound(s - 1)
		l2 = -1
	else:
		l1 = bit.lower_bound(s - 1)
		l2 = bit.lower_bound(s - 2)
	ans += calc_num(D[j], l1, l2, h1, h2) * (j + 1)
print(ans)


import math
import queue
import bisect
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)

def main():
	n = int(ipt())
	p = [int(i) for i in ipt().split()]
	ip = [0] * (n + 1)
	for (i, pi) in enumerate(p):
		ip[pi] = i
	ans = 0
	os = [-1, -1, n, n]
	for i in range(n, 0, -1):
		pl = ip[i]
		j = bisect.bisect_left(os, pl)
		(w, x, y, z) = (os[j - 2], os[j - 1], os[j], os[j + 1])
		ans += i * ((x - w) * (y - pl) + (pl - x) * (z - y))
		os.insert(j, pl)
	print(ans)
	return None
main()


class SegmentTree:

	def __init__(self, n, init_value):
		self.n = n
		n2 = 1
		while n2 < n:
			n2 <<= 1
		self.n2 = n2
		self.tree = [[init_value, init_value] for _ in range(n2 << 1)]
		self.ini = init_value

	def update(self, i, x):
		i += self.n2
		self.tree[i][0] = x
		while i > 1:
			i >>= 1
			sti = self.tree[i]
			if sti[0] > x:
				sti[1] = sti[0]
				sti[0] = x
			elif sti[1] > x:
				sti[1] = x

	def get(self, a, b):
		result = [self.ini, self.ini]
		q = [(1, 0, self.n2)]
		while q:
			(k, l, r) = q.pop()
			if a <= l and r <= b:
				stk = self.tree[k]
				if result[0] > stk[0]:
					result[1] = min(result[0], stk[1])
					result[0] = stk[0]
				elif result[1] > stk[0]:
					result[1] = stk[0]
				continue
			m = (l + r) // 2
			k <<= 1
			if a < m and l < b:
				q.append((k, l, m))
			if a < r and l < m:
				q.append((k + 1, m, r))
		return result

def solve(n, ppp):
	str = SegmentTree(n, n)
	right = []
	for i in range(n - 1, -1, -1):
		p = ppp[i]
		right.append(str.get(p, n))
		str.update(p - 1, i)
	right.reverse()
	ans = 0
	stl = SegmentTree(n, 1)
	for i in range(n):
		p = ppp[i]
		(l1, l2) = stl.get(p, n)
		(l1, l2) = (-l1, -l2)
		(r1, r2) = right[i]
		ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
		stl.update(p - 1, -i)
	return ans
n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))


n = int(input())
p = list(map(int, input().split()))
dn = {x: i for (i, x) in enumerate(p)}

def segfunc(x, y):
	return x + y
ide_ele = 0

class SegTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res
st = SegTree([0] * n, segfunc, 0)
ans = 0
st.update(dn[n], 1)
for i in range(n - 1, 0, -1):
	(l, r) = (0, dn[i])
	while r - l > 1:
		x = (l + r) // 2
		if st.query(x, dn[i] + 1) > 0:
			(l, r) = (x, r)
		else:
			(l, r) = (l, x)
	l0 = l if st.query(l, dn[i] + 1) == 0 else r
	if l0 == 0:
		l1 = -1
	else:
		(l, r) = (0, l0)
		while r - l > 1:
			x = (l + r) // 2
			if st.query(x, dn[i] + 1) > 1:
				(l, r) = (x, r)
			else:
				(l, r) = (l, x)
		l1 = l if st.query(l, dn[i] + 1) == 1 else r
	(l, r) = (dn[i], n - 1)
	while r - l > 1:
		x = (l + r) // 2
		if st.query(dn[i], x + 1) > 0:
			(l, r) = (l, x)
		else:
			(l, r) = (x, r)
	r0 = r if st.query(dn[i], r + 1) == 0 else l
	if r0 == n - 1:
		r1 = -1
	else:
		(l, r) = (r0, n - 1)
		while r - l > 1:
			x = (l + r) // 2
			if st.query(dn[i], x + 1) > 1:
				(l, r) = (l, x)
			else:
				(l, r) = (x, r)
		r1 = r if st.query(dn[i], r + 1) == 1 else l
	if l1 != -1:
		ans += (l0 - l1) * (r0 - dn[i] + 1) * i
	if r1 != -1:
		ans += (dn[i] - l0 + 1) * (r1 - r0) * i
	st.update(dn[i], 1)
print(ans)


class UnionFind:

	def __init__(self, size):
		self.parent = list(range(size))
		self.height = [0] * size
		self.size = [1] * size
		self.component = size

	def root(self, index):
		if self.parent[index] == index:
			return index
		rootIndex = self.root(self.parent[index])
		self.parent[index] = rootIndex
		return rootIndex

	def union(self, index1, index2):
		root1 = self.root(index1)
		root2 = self.root(index2)
		if root1 == root2:
			return
		self.component -= 1
		if self.height[root1] < self.height[root2]:
			self.parent[root1] = root2
			self.size[root2] += self.size[root1]
		else:
			self.parent[root2] = root1
			self.size[root1] += self.size[root2]
			if self.height[root1] == self.height[root2]:
				self.height[root1] += 1
		return

	def isSameRoot(self, index1, index2):
		return self.root(index1) == self.root(index2)

	def sizeOfSameRoot(self, index):
		return self.size[self.root(index)]

	def getComponent(self):
		return self.component
N = int(input())
INF = 10 ** 18
P = list(map(int, input().split()))
I = [-1] * (N + 1)
tree = UnionFind(N + 2)
for (i, p) in enumerate(P, start=1):
	I[p] = i
ans = 0
used = [False] * (N + 2)
for p in range(1, N):
	i = I[p]
	left = tree.sizeOfSameRoot(i - 1) if used[i - 1] else 0
	right = tree.sizeOfSameRoot(i + 1) if used[i + 1] else 0
	cnt = 0
	leftMx = i - (left + 1)
	if leftMx >= 1 and (not used[leftMx]):
		L = tree.sizeOfSameRoot(leftMx - 1) if leftMx - 1 >= 0 and used[leftMx - 1] else 0
		cnt += (L + 1) * (right + 1)
	rightMx = i + (right + 1)
	if rightMx <= N and (not used[rightMx]):
		R = tree.sizeOfSameRoot(rightMx + 1) if rightMx + 1 <= N and used[rightMx + 1] else 0
		cnt += (left + 1) * (R + 1)
	ans += cnt * p
	used[i] = True
	if used[i - 1]:
		tree.union(i, i - 1)
	if used[i + 1]:
		tree.union(i, i + 1)
print(ans)


N = int(input())
P = [int(a) - 1 for a in input().split()]
INV = [0] * N
for i in range(N):
	INV[P[i]] = i
NN = 17
MA = [-1] * ((1 << NN + 1) - 1)
MI = [N] * ((1 << NN + 1) - 1)

def update(a, x):
	i = (1 << NN) - 1 + a
	MI[i] = x
	MA[i] = x
	while True:
		i = (i - 1) // 2
		MI[i] = min(MI[2 * i + 1], MI[2 * i + 2])
		MA[i] = max(MA[2 * i + 1], MA[2 * i + 2])
		if i == 0:
			break

def rangemin(a, b):
	l = a + (1 << NN)
	r = b + (1 << NN)
	mi = N
	while l < r:
		if l % 2:
			mi = min(mi, MI[l - 1])
			l += 1
		if r % 2:
			r -= 1
			mi = min(mi, MI[r - 1])
		l >>= 1
		r >>= 1
	return mi

def rangemax(a, b):
	l = a + (1 << NN)
	r = b + (1 << NN)
	ma = -1
	while l < r:
		if l % 2:
			ma = max(ma, MA[l - 1])
			l += 1
		if r % 2:
			r -= 1
			ma = max(ma, MA[r - 1])
		l >>= 1
		r >>= 1
	return ma
ans = 0
for i in INV[::-1]:
	l1 = rangemax(0, i)
	l2 = rangemax(0, l1)
	r1 = rangemin(i + 1, N + 1)
	r2 = rangemin(r1 + 1, N + 1)
	pre = ans
	ans += (P[i] + 1) * ((i - l1) * (r2 - r1) + (l1 - l2) * (r1 - i))
	update(i, i)
print(ans)


import bisect
n = int(input())
p = [int(x) - 1 for x in input().split()]
p2 = sorted(enumerate(p), key=lambda x: x[1], reverse=True)
ans = 0
s = [-1, -1, n, n]
for (i, (idx, p)) in enumerate(p2):
	t = bisect.bisect_left(s, idx)
	s.insert(t, idx)
	l1 = s[t - 1]
	l2 = s[t - 2]
	r1 = s[t + 1]
	r2 = s[t + 2]
	ans += (p + 1) * ((idx - l1) * (r2 - r1) + (r1 - idx) * (l1 - l2))
print(ans)


import sys
import bisect
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A = [a - 1 for a in A]
AINV = [0] * N
for (i, x) in enumerate(A):
	AINV[x] = i
ANS = 0
LEN = N
BIT = [0] * (LEN + 1)

def update(v, w):
	while v <= LEN:
		BIT[v] += w
		v += v & -v

def getvalue(v):
	ANS = 0
	while v != 0:
		ANS += BIT[v]
		v -= v & -v
	return ANS
update(AINV[-1] + 1, 1)
ANS = 0

def search(score):
	if score <= 0:
		return 0
	if score > getvalue(N):
		return N + 1
	MIN = 1
	MAX = N
	while MIN != MAX:
		x = (MIN + MAX) // 2
		if getvalue(x) >= score:
			MAX = x
		else:
			MIN = x + 1
	return MIN
for i in range(N - 2, -1, -1):
	update(AINV[i] + 1, 1)
	sc = getvalue(AINV[i] + 1)
	ANS += (i + 1) * ((search(sc) - search(sc - 1)) * (search(sc + 2) - search(sc + 1)) + (search(sc - 1) - search(sc - 2)) * (search(sc + 1) - search(sc)))
print(ANS)


import sys
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def input():
	return sys.stdin.readline().rstrip()

def main():

	class BIT:

		def __init__(self, n):
			self.num = n
			self.dat = [0] * (self.num + 1)

		def add(self, i, x):
			i += 1
			while i <= self.num:
				self.dat[i] += x
				i += i & -i

		def sum(self, i):
			i += 1
			s = 0
			while i > 0:
				s += self.dat[i]
				i -= i & -i
			return s
	N = int(input())
	P = list(map(int, input().split()))
	P2 = [(P[i], i) for i in range(N)]
	P2.sort(reverse=True)
	b = BIT(N)

	def nibutan(i, num, ok, ng):
		b_sum_i = b.sum(i)
		while abs(ok - ng) > 1:
			mid = (ok + ng) // 2
			if solve(b_sum_i, i, num, mid):
				ok = mid
			else:
				ng = mid
		return ok

	def solve(b_sum_i, i, num, mid):
		if i > mid:
			if b_sum_i - b.sum(mid - 1) >= num:
				return True
		elif b.sum(mid) - b_sum_i >= num:
			return True
		return False
	ans = 0
	for p in P2:
		x = b.sum(p[1])
		y = b.sum(N - 1)
		if x >= 1 or y - x >= 1:
			s = nibutan(p[1], 1, -1, p[1])
			t = nibutan(p[1], 2, -1, p[1])
			u = nibutan(p[1], 1, N, p[1])
			v = nibutan(p[1], 2, N, p[1])
			if x >= 1:
				ans += p[0] * (s - t) * (u - p[1]) if s > -1 else 0
			if y - x >= 1:
				ans += p[0] * (v - u) * (p[1] - s) if u < N else 0
		b.add(p[1], 1)
	print(ans)
main()


n = int(input())
p = list(map(int, input().split()))
r = list(range(n))
l = list(range(n))
I = [-1] * (n + 1)
for (i, P) in enumerate(p):
	I[P] = i
ans = 0
for (N, index) in enumerate(I[1:], 1):
	L = index - 1
	if L >= 0:
		L = l[L]
	R = index + 1
	if R < n:
		R = r[R]
	l[R - 1] = L
	r[L + 1] = R
	if L >= 0:
		L2 = L - 1
		if L2 >= 0:
			L2 = l[L2]
		ans += N * (L - L2) * (R - index)
	if R < n:
		R2 = R + 1
		if R2 < n:
			R2 = r[R2]
		ans += N * (index - L) * (R2 - R)
print(ans)


n = int(input())
p = [(int(x), i) for (i, x) in enumerate(input().split())]
p.sort(reverse=True)

class BinaryIndexedTree:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (self.n + 1)

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

	def add(self, i, x):
		if i <= 0:
			return
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def lower_bound(self, x):
		if x <= 0:
			return 0
		(cur, s, k) = (0, 0, 1 << self.n.bit_length() - 1)
		while k:
			nxt = cur + k
			if nxt <= self.n and s + self.data[nxt] < x:
				s += self.data[nxt]
				cur = nxt
			k >>= 1
		return cur + 1
bit = BinaryIndexedTree(n)
ans = 0
for (x, i) in p:
	i += 1
	bit.add(i, 1)
	idx = bit.sum(i)
	(l1, l2) = (bit.lower_bound(idx - 1), bit.lower_bound(idx - 2))
	(r1, r2) = (bit.lower_bound(idx + 1), bit.lower_bound(idx + 2))
	ans += ((l1 - l2) * (r1 - i) + (i - l1) * (r2 - r1)) * x
print(ans)


import sys
input = sys.stdin.readline

class RmaxQ:

	def __init__(self, original):
		self.n = len(original)
		self.INF = -float('inf')
		self.N0 = 1 << (self.n - 1).bit_length()
		self.seg = [self.INF] * (self.N0 << 1)
		for (i, j) in enumerate(original, self.N0):
			self.seg[i] = j
		for i in range(self.N0 - 1, 0, -1):
			self.seg[i] = max(self.seg[2 * i], self.seg[2 * i + 1])

	def get(self, i):
		return self.seg[i + self.N0]

	def update(self, i, x):
		i += self.N0
		self.seg[i] = x
		while i > 1:
			y = self.seg[i ^ 1]
			if y >= x:
				break
			i >>= 1
			self.seg[i] = x

	def add(self, i, d):
		self.update(i, self.get(i) + d)

	def query(self, l, r):
		res = self.INF
		l += self.N0
		r += self.N0
		while l < r:
			if r & 1:
				res = max(res, self.seg[r - 1])
			if l & 1:
				res = max(res, self.seg[l])
				l += 1
			l >>= 1
			r >>= 1
		return res
n = int(input())
P = list(map(int, input().split()))
seg = RmaxQ(P)

def bs(i, p, right):
	if right:
		ok = i
		ng = n
		while ng - ok > 1:
			mid = (ok + ng) // 2
			if seg.query(i + 1, mid + 1) > p:
				ng = mid
			else:
				ok = mid
	else:
		ok = i
		ng = -1
		while ok - ng > 1:
			mid = (ok + ng) // 2
			if seg.query(mid, i) > p:
				ng = mid
			else:
				ok = mid
	return ng
ans = 0
for (i, p) in enumerate(P):
	r1 = bs(i, p, True)
	r2 = bs(r1, p, True)
	l1 = bs(i, p, False)
	l2 = bs(l1, p, False)
	ans += p * ((l1 - l2) * (r1 - i) + (i - l1) * (r2 - r1))
print(ans)


import sys
input = sys.stdin.readline

class BIT:

	def __init__(self, size):
		self.bit = [0] * (size + 1)
		self.size = size

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

	def add(self, i, x):
		i += 1
		while i <= self.size:
			self.bit[i] += x
			i += i & -i
N = int(input())
P = list(map(int, input().split()))
idx = [-1] * (N + 1)
for (i, p) in enumerate(P):
	idx[p] = i + 1
bit = BIT(N + 1)
bit.add(0, 1)
ans = 0

def bin_search(target):
	(lb, ub) = (-1, N + 1)
	while ub - lb > 1:
		m = (lb + ub) // 2
		if bit.sum(m) < target:
			lb = m
		else:
			ub = m
	return ub
for p in range(1, N + 1)[::-1]:
	c = idx[p]
	s = bit.sum(c)
	a = bin_search(s - 1)
	b = bin_search(s)
	d = bin_search(s + 1)
	e = bin_search(s + 2)
	ans += p * ((b - a) * (d - c) + (c - b) * (e - d))
	bit.add(c, 1)
print(ans)


import sys
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
n = ni()
a = na()
st = []
ans = 0
gans = 0
for i in range(n):
	v = a[i]
	l = 0
	bst = []
	while len(st) > 0 and st[-1][1] < v:
		h = st.pop(-1)
		ans -= h[1] * h[2]
		if h[0] < v:
			(h[0], h[1]) = (v, h[0])
		else:
			h[1] = v
		ans += h[1] * h[2]
		if len(bst) > 0 and bst[-1][0] == h[0] and (bst[-1][1] == h[1]):
			bst[-1][2] += h[2]
		else:
			bst.append(h)
	st.extend(bst[::-1])
	st.append([v, 0, 1])
	gans += ans
print(gans)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter
n = int(readline())
ppp = list(map(int, readline().split()))

class Bit:

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

	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, x):
		sum_ = 0
		pos = 0
		for i in range(self.depth, -1, -1):
			k = pos + (1 << i)
			if k <= self.size and sum_ + self.tree[k] < x:
				sum_ += self.tree[k]
				pos += 1 << i
		return pos + 1
q = sorted(enumerate(ppp, 1), key=itemgetter(1), reverse=True)
bit = Bit(n + 4)
bit.add(1, 1)
bit.add(2, 1)
bit.add(n + 3, 1)
bit.add(n + 4, 1)
ans = 0
for (i, p) in q:
	f = bit.sum(i + 2)
	LL = max(2, bit.lower_bound(f - 1))
	LR = bit.lower_bound(f)
	RL = bit.lower_bound(f + 1)
	RR = min(n + 3, bit.lower_bound(f + 2))
	ans += p * ((i + 2 - LR) * (RR - RL) + (LR - LL) * (RL - i - 2))
	bit.add(i + 2, 1)
print(ans)


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 bisect_plus(self, i, t):
		L = i
		R = self.size
		R_prev = R
		sum_i = self.sum(i)
		while True:
			range_sum = self.sum(R) - sum_i
			if range_sum < t:
				if R == self.size:
					return self.size + 1
				(L, R) = (R, R_prev)
			else:
				R_prev = R
				R = (L + R + 1) // 2
				if R == R_prev:
					return R

	def bisect_minus(self, i, t):
		L = 1
		R = i
		L_prev = L
		sum_i = self.sum(i - 1)
		while True:
			range_sum = sum_i - self.sum(L - 1)
			if range_sum < t:
				if L == 1:
					return 0
				(L, R) = (L_prev, L)
			else:
				L_prev = L
				L = (L + R) // 2
				if L == L_prev:
					return L
N = int(input())
P = list(map(int, input().split()))
place = [-1] * (N + 1)
for i in range(N):
	p = P[i]
	place[p] = i
ans = 0
big_place = Bit(N)
big_place.add(place[N] + 1, 1)
for i in range(N - 1, 0, -1):
	pos = place[i] + 1
	right = big_place.bisect_plus(pos, 1)
	right2 = big_place.bisect_plus(pos, 2)
	left = big_place.bisect_minus(pos, 1)
	left2 = big_place.bisect_minus(pos, 2)
	if left > 0:
		left_cand = left - left2
	else:
		left_cand = 0
	right_cand = right - pos
	ans += i * left_cand * right_cand
	if right < N + 1:
		right_cand = right2 - right
	else:
		right_cand = 0
	left_cand = pos - left
	ans += i * left_cand * right_cand
	big_place.add(pos, 1)
print(ans)


INF = 10 ** 9

class RmQ:

	def __init__(self, a):
		self.n = len(a)
		self.size = 2 ** (self.n - 1).bit_length()
		self.data_min = [INF] * (2 * self.size - 1)
		self.initialize(a)

	def initialize(self, a):
		for i in range(self.n):
			self.data_min[self.size + i - 1] = a[i]
		for i in range(self.size - 2, -1, -1):
			self.data_min[i] = min(self.data_min[i * 2 + 1], self.data_min[i * 2 + 2])

	def update(self, k, x):
		k += self.size - 1
		self.data_min[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data_min[k] = min(self.data_min[2 * k + 1], self.data_min[2 * k + 2])

	def query(self, l, r):
		L = l + self.size
		R = r + self.size
		s = INF
		while L < R:
			if R & 1:
				R -= 1
				s = min(s, self.data_min[R - 1])
			if L & 1:
				s = min(s, self.data_min[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return s

class RMQ:

	def __init__(self, a):
		self.n = len(a)
		self.size = 2 ** (self.n - 1).bit_length()
		self.data_max = [-INF] * (2 * self.size - 1)
		self.initialize(a)

	def initialize(self, a):
		for i in range(self.n):
			self.data_max[self.size + i - 1] = a[i]
		for i in range(self.size - 2, -1, -1):
			self.data_max[i] = max(self.data_max[i * 2 + 1], self.data_max[i * 2 + 2])

	def update(self, k, x):
		k += self.size - 1
		self.data_max[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data_max[k] = max(self.data_max[2 * k + 1], self.data_max[2 * k + 2])

	def query(self, l, r):
		L = l + self.size
		R = r + self.size
		s = -INF
		while L < R:
			if R & 1:
				R -= 1
				s = max(s, self.data_max[R - 1])
			if L & 1:
				s = max(s, self.data_max[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return s
n = int(input())
a = [int(item) for item in input().split()]
indexes = [0] * n
for (i, item) in enumerate(a):
	indexes[item - 1] = i
indexes.reverse()
a_min = [-1] * 2 + [INF] * n + [n] * 2
a_max = [-1] * 2 + [-INF] * n + [n] * 2
rMq = RMQ(a_max)
rmq = RmQ(a_min)
ans = 0
for (i, idx) in enumerate(indexes):
	num = n - i
	L1 = rMq.query(0, idx + 2)
	L2 = rMq.query(0, L1 + 2)
	R1 = rmq.query(idx + 2, n + 4)
	R2 = rmq.query(R1 + 3, n + 4)
	ans += (L1 - L2) * (R1 - idx) * num
	ans += (idx - L1) * (R2 - R1) * num
	rMq.update(idx + 2, idx)
	rmq.update(idx + 2, idx)
print(ans)


N = int(input())
P = [int(i) for i in input().split()]
ind = [0] * (N + 1)
for i in range(N):
	ind[P[i]] = i + 1
ans = 0
l = [0] + [f for f in range(N + 1)]
r = [f + 1 for f in range(N + 1)] + [N + 1]
for j in range(1, N + 1):
	f = ind[j]
	l1 = l[f]
	l2 = l[l1]
	r1 = r[f]
	r2 = r[r1]
	ans += ((l1 - l2) * (r1 - f) + (f - l1) * (r2 - r1)) * j
	l[r1] = l1
	r[l1] = r1
print(ans)


class SegTree:

	def segfunc(self, x, y):
		return x + y

	def __init__(self, ide, n, init_val):
		self.ide_ele = ide
		self.num = 2 ** (n - 1).bit_length()
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k:
			k = (k - 1) // 2
			self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = self.segfunc(res, self.seg[p])
			if q & 1 == 1:
				res = self.segfunc(res, self.seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = self.segfunc(res, self.seg[p])
		else:
			res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
		return res

def main():
	n = int(input())
	P = list(map(int, input().split()))
	ans = 0
	arr = [[P[i], i] for i in range(n)]
	arr.sort(key=lambda x: -x[0])
	seg = SegTree(0, n, [0] * n)
	for (v, idx) in arr:
		seg.update(idx, 1)
		if idx < n - 1 and seg.query(idx + 1, n) > 0:
			(L, R) = (idx, n)
			while L + 1 < R:
				M = (L + R) // 2
				if seg.query(idx + 1, M + 1) < 1:
					L = M
				else:
					R = M
			x = R
			(L, R) = (x, n)
			while L + 1 < R:
				M = (L + R) // 2
				if seg.query(idx + 1, M + 1) < 2:
					L = M
				else:
					R = M
			r_range = R - x
			(L, R) = (-1, idx)
			while L + 1 < R:
				M = (L + R + 1) // 2
				if seg.query(M, idx) == 0:
					R = M
				else:
					L = M
			l_range = idx - L
			ans += v * l_range * r_range
		if 0 < idx and seg.query(0, idx) > 0:
			(L, R) = (idx, n)
			while L + 1 < R:
				M = (L + R) // 2
				if seg.query(idx + 1, M + 1) == 0:
					L = M
				else:
					R = M
			r_range = R - idx
			(L, R) = (0, idx)
			while L + 1 < R:
				M = (L + R) // 2
				if seg.query(M, idx) < 1:
					R = M
				else:
					L = M
			x = L
			(L, R) = (-1, x)
			while L + 1 < R:
				M = (L + R + 1) // 2
				if seg.query(M, idx) < 2:
					R = M
				else:
					L = M
			l_range = x - L
			ans += v * l_range * r_range
	print(ans)
main()


class Bit:

	def __init__(self, n):
		self.bl = n.bit_length()
		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 bs(self, x, side='l'):
		k = 1 << self.bl - 1
		i = 0
		sm = 0
		flg = int(side != 'l')
		while k:
			while i + k > self.size:
				k //= 2
			if sm + self.tree[i + k] < x + flg:
				sm += self.tree[i + k]
				i += k
			k //= 2
		return i + 1
n = int(input())
a = list(map(int, input().split()))
da = {a[i]: i + 1 for i in range(n)}
ans = 0
bit = Bit(n)
for i in range(n, 0, -1):
	idx = da[i]
	x = bit.sum(idx)
	l2 = bit.bs(x - 1, 'l')
	l1 = bit.bs(x, 'l')
	r1 = bit.bs(x + 1, 'l')
	r2 = bit.bs(x + 2, 'l')
	if i == n:
		bit.add(idx, 1)
		continue
	if l1 == 1 or x == 1:
		l2 = 0
	if r1 == n + 1:
		r2 = n + 2
	if x == 0:
		ans += idx * (r2 - r1) * i
	elif r1 == n + 1:
		ans += (n - idx + 1) * (l1 - l2) * i
	else:
		if r1 < r2:
			ans += (r2 - r1) * (idx - l1) * i
		if l2 < l1:
			ans += (l1 - l2) * (r1 - idx) * i
	bit.add(idx, 1)
print(ans)


N = int(input())
P = [int(i) for i in input().split(' ')]
pos = [0] * (N + 1)
for i in range(N):
	pos[P[i]] = i + 1
l = [0] + [i for i in range(N + 1)]
r = [i + 1 for i in range(N + 1)] + [N + 1]
ans = 0
for i in range(1, N + 1):
	idx = pos[i]
	(l1, r1) = (l[idx], r[idx])
	(l2, r2) = (l[l1], r[r1])
	ans += i * ((l1 - l2) * (r1 - idx) + (idx - l1) * (r2 - r1))
	(l[r1], r[l1]) = (l1, r1)
print(ans)


class BITbisect:

	def __init__(self, max):
		self.max = max
		self.data = [0] * (self.max + 1)

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

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

	def insert(self, x):
		self.add(x, 1)

	def delete(self, x):
		self.add(x, -1)

	def count(self, x):
		return self.query_sum(x) - self.query_sum(x - 1)

	def length(self):
		return self.query_sum(self.max)

	def search(self, c):
		c += 1
		s = 0
		ind = 0
		l = self.max.bit_length()
		for i in reversed(range(l)):
			if ind + (1 << i) <= self.max:
				if s + self.data[ind + (1 << i)] < c:
					s += self.data[ind + (1 << i)]
					ind += 1 << i
		if ind == self.max:
			return False
		return ind + 1

	def bisect_right(self, x):
		return self.query_sum(x)

	def bisect_left(self, x):
		if x == 1:
			return 0
		return self.query_sum(x - 1)

	def display(self):
		print('inside BIT:', end=' ')
		for x in range(1, self.max + 1):
			if self.count(x):
				c = self.count(x)
				for _ in range(c):
					print(x, end=' ')
		print()
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
bit = BITbisect(N)
co_to_ind = [0] * (N + 1)
for i in range(N):
	co_to_ind[A[i]] = i + 1
	bit.insert(i + 1)
ans = 0
for n in range(1, N + 1):
	ind = co_to_ind[n]
	seq = bit.bisect_left(ind)
	L = bit.length()
	if seq >= 2:
		l1 = bit.search(seq - 1)
		l0 = bit.search(seq - 2)
	elif seq == 1:
		l1 = bit.search(seq - 1)
		l0 = 0
	else:
		l1 = 0
		l0 = 0
	if L - 1 - seq >= 2:
		r1 = bit.search(seq + 1)
		r0 = bit.search(seq + 2)
	elif L - 1 - seq == 1:
		r1 = bit.search(seq + 1)
		r0 = N + 1
	else:
		r1 = N + 1
		r0 = N + 1
	ans += ((ind - l1) * (r0 - r1) + (l1 - l0) * (r1 - ind)) * n
	bit.delete(ind)
print(ans)


import itertools
import os
import sys
from collections import defaultdict
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))
N += 1
P = [0] + P

def test(A):
	N = len(A)
	ret = 0
	for i in range(N - 1):
		for j in range(i + 1, N):
			b = A[i:j + 1].copy()
			b.sort()
			ret += b[-2]
	return ret

class BinaryIndexedTree:

	def __init__(self, size):
		self._bit = [0] * size
		self._size = size

	def add(self, i, w):
		x = i + 1
		while x <= self._size:
			self._bit[x - 1] += w
			x += x & -x

	def sum(self, i):
		ret = 0
		x = i + 1
		while x > 0:
			ret += self._bit[x - 1]
			x -= x & -x
		return ret

	def __len__(self):
		return self._size

def bisect_left_callable(fn, x, lo, hi):
	while lo < hi:
		mid = (lo + hi) // 2
		if fn(mid) < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def argsort(li):
	return [i for (_, i) in sorted([(a, i) for (i, a) in enumerate(li)], reverse=True)]
bit = BinaryIndexedTree(size=N)
idx = argsort(P)
ans = 0
for i in idx[:-1]:
	cnt = bit.sum(i)
	l1 = bisect_left_callable(lambda k: bit.sum(k), cnt, lo=0, hi=i)
	l2 = bisect_left_callable(lambda k: bit.sum(k), cnt - 1, lo=0, hi=i)
	r1 = bisect_left_callable(lambda k: bit.sum(k), cnt + 1, lo=i + 1, hi=N)
	r2 = bisect_left_callable(lambda k: bit.sum(k), cnt + 2, lo=i + 1, hi=N)
	a = (r1 - i) * (l1 - l2)
	b = (i - l1) * (r2 - r1)
	ans += P[i] * (a + b)
	bit.add(i, 1)
print(ans)


n = int(input())
P = list(map(int, input().split()))
num = 2 ** n.bit_length()
ele = 0
SEG = [ele] * (2 * num)

def func(a, b):
	return a + b

def update(idx, x):
	idx += num
	SEG[idx] += x
	idx //= 2
	while idx > 0:
		SEG[idx] = func(SEG[2 * idx], SEG[2 * idx + 1])
		idx //= 2

def query(a, b):
	a += num
	b += num - 1
	res = ele
	while b - a > 0:
		if a & 1 == 1:
			res = func(res, SEG[a])
			a += 1
		if b & 1 == 0:
			res = func(res, SEG[b])
			b -= 1
		a //= 2
		b //= 2
	if b == a:
		res = func(res, SEG[b])
	return res

def nibutan1(a):
	ok1 = a
	ng = n
	while ng - ok1 > 1:
		mid = (ng + ok1) // 2
		if query(a, mid + 1) == 0:
			ok1 = mid
		else:
			ng = mid
	if ok1 == n - 1:
		return (n - 1, n - 1)
	ok2 = 0
	ok2 += ok1
	ng = n
	while ng - ok2 > 1:
		mid = (ng + ok2) // 2
		if query(a, mid + 1) == 1:
			ok2 = mid
		else:
			ng = mid
	return (ok1, ok2)

def nibutan2(a):
	ok1 = a
	ng = -1
	while ok1 - ng > 1:
		mid = (ng + ok1) // 2
		if query(mid, a + 1) == 0:
			ok1 = mid
		else:
			ng = mid
	if ok1 == 0:
		return (0, 0)
	ok2 = 0
	ok2 += ok1
	ng = -1
	while ok2 - ng > 1:
		mid = (ng + ok2) // 2
		if query(mid, a + 1) == 1:
			ok2 = mid
		else:
			ng = mid
	return (ok1, ok2)
A = [None] * n
for (idx, v) in enumerate(P):
	A[idx] = (v, idx)
A.sort(reverse=True)
ans = 0
for (v, idx) in A:
	(migi1, migi2) = nibutan1(idx)
	(hidari1, hidari2) = nibutan2(idx)
	if migi1 == n - 1 and hidari1 == 0:
		pass
	elif migi1 == n - 1:
		ans += v * (migi1 - idx + 1) * (hidari1 - hidari2)
	elif hidari1 == 0:
		ans += v * (idx - hidari1 + 1) * (migi2 - migi1)
	else:
		ans += v * (migi1 - idx + 1) * (hidari1 - hidari2)
		ans += v * (idx - hidari1 + 1) * (migi2 - migi1)
	update(idx, 1)
print(ans)


import bisect

def main():
	N = int(input())
	P = list(map(int, input().split(' ')))
	Q = [0] + P + [N + 1]
	index_q = [0 for _ in range(len(Q))]
	for (i, q) in enumerate(Q):
		index_q[q] = i
	I = [0, 0, N + 1, N + 1]
	ans = 0
	for c in range(N, 0, -1):
		i = index_q[c]
		j = bisect.bisect_left(I, i)
		(w, x, y, z) = (I[j - 2], I[j - 1], I[j], I[j + 1])
		ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
		I.insert(j, i)
	print(ans)
main()


n = int(input())
p = list(map(int, input().split()))
f = [0] * (n + 1)
for i in range(n):
	f[p[i]] = i + 1
l = [0] + [i for i in range(n + 1)]
r = [i + 1 for i in range(n + 1)] + [n + 1]
ans = 0
for i in range(1, n + 1):
	x = f[i]
	(l1, r1) = (l[x], r[x])
	(l2, r2) = (l[l1], r[r1])
	ans += i * ((l1 - l2) * (r1 - x) + (x - l1) * (r2 - r1))
	(l[r1], r[l1]) = (l1, r1)
print(ans)


import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
INF = float('inf')

class BIT:

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

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

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

	def search(self, val):
		i = 0
		s = 0
		step = 1 << self.size.bit_length() - 1
		while step:
			if i + step <= self.size and s + self.tree[i + step] < val:
				i += step
				s += self.tree[i]
			step //= 2
		return i + 1

def sol():
	N = int(input())
	P = [None] + list(map(int, input().split()))
	pToI = {p: i for (i, p) in enumerate(P[1:], 1)}
	tree = BIT(N)
	ans = 0
	for p in range(1, N + 1)[::-1]:
		i = pToI[p]
		left = tree.sum(i)
		tree.add(i)
		right = N - p - left
		L1 = tree.search(left - 1) if left >= 2 else 0
		L2 = tree.search(left) if left >= 1 else 0
		R1 = tree.search(left + 2) if right >= 1 else N + 1
		R2 = tree.search(left + 3) if right >= 2 else N + 1
		cnt = 0
		if L2 != 0:
			cnt += (L2 - L1) * (R1 - i)
		if R1 != 0:
			cnt += (R2 - R1) * (i - L2)
		ans += cnt * p
	print(ans)
sol()


import bisect
N = int(input())
P = list(map(int, input().split()))
P_inv = [0] * N
for i in range(N):
	P_inv[P[i] - 1] = i
c = [-1, -1, P_inv[N - 1], N, N]
cnt = 0
for i in reversed(range(N - 1)):
	l = bisect.bisect_left(c, P_inv[i])
	cnt += (i + 1) * ((c[l - 1] - c[l - 2]) * (c[l] - P_inv[i]) + (P_inv[i] - c[l - 1]) * (c[l + 1] - c[l]))
	bisect.insort_left(c, P_inv[i])
print(cnt)


N = int(input())
Ps = list(map(int, input().split()))
iPs = [0] * (N + 1)
for (iP, A) in enumerate(Ps):
	iPs[A] = iP
ans = 0
iLs = list(range(N + 1))
iRs = list(range(N + 1))
for P in range(1, N + 1):
	i = iPs[P]
	(iL, iR) = (iLs[i], iRs[i])
	if iL <= 1:
		iL2 = 0
	else:
		iL2 = iLs[iL - 1]
	if iR >= N - 2:
		iR2 = N - 1
	else:
		iR2 = iRs[iR + 1]
	num = 0
	if iL != 0:
		num += (iL - iL2) * (iR - i + 1)
	if iR != N - 1:
		num += (i - iL + 1) * (iR2 - iR)
	ans += P * num
	iLs[iR + 1] = iL
	iRs[iL - 1] = iR
print(ans)


class Node:

	def __init__(self, v):
		self.v = v
		self.p = None
		self.n = None

	def delete(self):
		if self.p:
			self.p.n = self.n
		if self.n:
			self.n.p = self.p
N = int(input())
pp = list(map(int, input().split()))
nn = dict()
prev = None
for (i, p) in enumerate(pp):
	n = Node(i)
	if prev:
		prev.n = n
		n.p = prev
	nn[p] = n
	prev = n
s = 0
for x in range(1, N):
	c = nn[x]
	ci = c.v
	pi = c.p.v if c.p else -1
	ni = c.n.v if c.n else N
	if c.p:
		ppi = c.p.p.v if c.p.p else -1
		s += x * (pi - ppi) * (ni - ci)
	if c.n:
		nni = c.n.n.v if c.n.n else N
		s += x * (ci - pi) * (nni - ni)
	c.delete()
print(s)


import sys

def solve(N: int, P: 'List[int]'):
	pos = {n: i + 1 for (i, n) in enumerate(P)}
	L1 = list(range(-1, N + 1))
	L1[0] = 0
	L2 = list(range(-2, N))
	L2[0] = 0
	L2[1] = 0
	R1 = list(range(1, N + 3))
	R1[-1] = N + 1
	R2 = list(range(2, N + 4))
	R2[-1] = N + 1
	R2[-2] = N + 1
	res = 0
	for i in range(1, N + 1):
		s = pos[i]
		num = 0
		num += (R2[s] - R1[s]) * (s - L1[s])
		num += (L1[s] - L2[s]) * (R1[s] - s)
		res += i * num
		L1[R1[s]] = L1[s]
		L2[R1[s]] = L2[s]
		L2[R2[s]] = L1[s]
		R1[L1[s]] = R1[s]
		R2[L1[s]] = R2[s]
		R2[L2[s]] = R1[s]
	print(res)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	P = [int(next(tokens)) for _ in range(N)]
	solve(N, P)
main()


def make_tree(n):
	i = 2
	while True:
		if i >= n * 2:
			tree = [-1] * i
			break
		else:
			i *= 2
	return tree

def initialization(tree, a):
	l = len(tree) // 2
	for i in range(l, l + len(a)):
		tree[i] = a[i - l]
	for i in range(l - 1, 0, -1):
		tree[i] = max(tree[2 * i], tree[2 * i + 1])
	return

def update(tree, i, x):
	i += len(tree) // 2
	tree[i] = x
	i //= 2
	while True:
		if i == 0:
			break
		tree[i] = max(tree[2 * i], tree[2 * i + 1])
		i //= 2
	return

def find(tree, s, t):
	s += len(tree) // 2
	t += len(tree) // 2
	ans = -1
	while True:
		if s > t:
			break
		if s % 2 == 0:
			s //= 2
		else:
			ans = max(ans, tree[s])
			s = (s + 1) // 2
		if t % 2 == 1:
			t //= 2
		else:
			ans = max(ans, tree[t])
			t = (t - 1) // 2
	return ans
n = int(input())
p = list(map(int, input().split()))
q = [0] * n
tree = make_tree(n)
a = [[-1, -1] for _ in range(n)]
b = [[-1, -1] for _ in range(n)]
update(tree, p[0] - 1, 0)
for i in range(1, n):
	a[i][0] = find(tree, p[i], n - 1)
	if not a[i][0] == -1:
		update(tree, p[a[i][0]] - 1, -1)
		a[i][1] = find(tree, p[i], n - 1)
		update(tree, p[a[i][0]] - 1, a[i][0])
	update(tree, p[i] - 1, i)
initialization(tree, [-1] * n)
update(tree, p[-1] - 1, 0)
for i in range(1, n):
	j = n - i - 1
	b[j][0] = find(tree, p[j], n - 1)
	if not b[j][0] == -1:
		update(tree, p[n - b[j][0] - 1] - 1, -1)
		b[j][1] = find(tree, p[j], n - 1)
		update(tree, p[n - b[j][0] - 1] - 1, b[j][0])
	update(tree, p[j] - 1, i)
	if not b[j][0] == -1:
		b[j][0] = n - b[j][0] - 1
	if not b[j][1] == -1:
		b[j][1] = n - b[j][1] - 1
ans = 0
for i in range(n):
	if p[i] == n:
		continue
	if b[i][0] == -1:
		if not a[i][1] == -1:
			x = (n - i) * (a[i][0] - a[i][1])
		elif not a[i][0] == -1:
			x = (n - i) * (a[i][0] + 1)
	elif a[i][0] == -1:
		if not b[i][1] == -1:
			x = (i + 1) * (b[i][1] - b[i][0])
		elif not b[i][0] == -1:
			x = (i + 1) * (n - b[i][0])
	elif a[i][1] == b[i][1] == -1:
		x = (i - a[i][0]) * (n - b[i][0]) + (b[i][0] - i) * (a[i][0] + 1)
	elif b[i][1] == -1:
		x = (b[i][0] - i) * (a[i][0] - a[i][1]) + (i - a[i][0]) * (n - b[i][0])
	elif a[i][1] == -1:
		x = (i - a[i][0]) * (b[i][1] - b[i][0]) + (b[i][0] - i) * (a[i][0] + 1)
	else:
		x = (i - a[i][0]) * (b[i][1] - b[i][0]) + (b[i][0] - i) * (a[i][0] - a[i][1])
	ans += p[i] * x
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(input())
P = list(map(int, input().split()))
p_to_i = {a: i for (i, a) in enumerate(P, 1)}
BIT = [0] * (N + 1)

def BIT_query(idx):
	res_sum = 0
	while idx > 0:
		res_sum += BIT[idx]
		idx -= idx & -idx
	return res_sum

def BIT_update(idx, x):
	while idx <= N:
		BIT[idx] += x
		idx += idx & -idx
	return

def BIT_search(x):
	i = 0
	step = 1 << N.bit_length() - 1
	while step:
		if i + step <= N and BIT[i + step] < x:
			x -= BIT[i + step]
			i += step
		step >>= 1
	return i + 1
ans = 0
for p in range(N, 0, -1):
	i = p_to_i[p]
	LEFT = BIT_query(i)
	RIGHT = N - p - LEFT
	cnt = 0
	if LEFT == 0 and RIGHT == 0:
		BIT_update(i, 1)
		continue
	a = BIT_search(LEFT - 1) if LEFT >= 2 else 0
	b = BIT_search(LEFT) if LEFT >= 1 else 0
	c = BIT_search(LEFT + 1) if RIGHT >= 1 else N + 1
	d = BIT_search(LEFT + 2) if RIGHT >= 2 else N + 1
	if b != 0:
		cnt += (b - a) * (c - i)
	if c != N + 1:
		cnt += (d - c) * (i - b)
	BIT_update(i, 1)
	ans += p * cnt
print(ans)


import bisect
N = int(input())
P = sorted(enumerate(map(int, input().split())), key=lambda x: x[1])[::-1]
used = [-1, P[0][0], N]
ans = 0
for (i, p) in P[1:]:
	idx = bisect.bisect_left(used, i)
	d = 0
	if idx != 1:
		d += (used[idx] - i) * (used[idx - 1] - used[idx - 2])
	if idx != len(used) - 1:
		d += (i - used[idx - 1]) * (used[idx + 1] - used[idx])
	ans += p * d
	used.insert(idx, i)
print(ans)


class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 10)

	def add(self, x, w):
		while x <= self.n:
			self.bit[x] += w
			x += x & -x

	def sum(self, x):
		cnt = 0
		while x > 0:
			cnt += self.bit[x]
			x -= x & -x
		return cnt

	def psum(self, a, b):
		return self.sum(b - 1) - self.sum(a - 1)

	def bisect(self, w):
		x = 0
		k = 1
		while k < self.n:
			k *= 2
		while k > 0:
			if x + k <= self.n and self.bit[x + k] < w:
				w -= self.bit[x + k]
				x += k
			k //= 2
		return x + 1
n = int(input())
ps = list(map(int, input().split()))
inds = [0] * (n + 1)
for (i, p) in enumerate(ps):
	inds[p] = i + 1
bit = BIT(n)
cnt = 0
for p in range(n, 0, -1):
	ind = inds[p]
	nl = bit.sum(ind)
	nr = n - p - nl
	bit.add(ind, 1)
	ixl2 = bit.bisect(nl - 1) if nl >= 2 else 0
	ixl1 = bit.bisect(nl) if nl >= 1 else 0
	ixr1 = bit.bisect(nl + 2) if nr >= 1 else n + 1
	ixr2 = bit.bisect(nl + 3) if nr >= 2 else n + 1
	tmp = 0
	tmp += (ixl1 - ixl2) * (ixr1 - ind)
	tmp += (ixr2 - ixr1) * (ind - ixl1)
	cnt += p * tmp
print(cnt)


n = int(input())
p = list(map(int, input().split()))

def init(init_val):
	for i in range(n):
		seg[i + num - 1] = init_val[i]
	for i in range(num - 2, -1, -1):
		seg[i] = max(seg[2 * i + 1], seg[2 * i + 2])

def update(k, x):
	k += num - 1
	seg[k] = x
	while k + 1:
		k = (k - 1) // 2
		seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2])

def query(p, q):
	if q <= p:
		return ide_ele
	p += num - 1
	q += num - 2
	res = ide_ele
	while q - p > 1:
		if p & 1 == 0:
			res = max(res, seg[p])
		if q & 1 == 1:
			res = max(res, seg[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = max(res, seg[p])
	else:
		res = max(max(res, seg[p]), seg[q])
	return res
ide_ele = -1
num = 2 ** n.bit_length()
seg = [ide_ele] * 2 * num
res = 0
s = [0] * (n + 1)
update(p[0], 0)
for i in range(1, n):
	k1 = query(p[i], n + 1)
	if k1 != -1:
		update(p[k1], -1)
		k2 = query(p[i], n + 1)
		s[i] = p[i] * (k1 - k2) + s[k1]
		res += s[i]
		update(p[k1], k1)
	update(p[i], i)
ide_ele = -n
seg = [ide_ele] * 2 * num
s = [0] * (n + 1)
update(p[-1], 1 - n)
for i in range(n - 2, -1, -1):
	k1 = query(p[i], n + 1)
	if k1 != -n:
		update(p[-k1], -n)
		k2 = query(p[i], n + 1)
		s[i] = p[i] * (k1 - k2) + s[-k1]
		res += s[i]
		update(p[-k1], k1)
	update(p[i], -i)
print(res)


class BIT:

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

	def BIT_add(self, i):
		while i <= self.N:
			self.tree[i] += 1
			i += i & -i

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

	def BIT_search(self, x):
		i = 0
		s = 0
		step = 1 << self.N.bit_length() - 1
		while step:
			if i + step <= self.N and s + self.tree[i + step] < x:
				i += step
				s += self.tree[i]
			step >>= 1
		return i + 1
N = int(input())
bit = BIT(N)
p = [None] + [int(c) for c in input().split()]
p_to_i = [None] * (N + 1)
for (i, x) in enumerate(p[1:], 1):
	p_to_i[x] = i
ans = 0
for x in range(N, 0, -1):
	c = p_to_i[x]
	L = bit.BIT_sum(c)
	bit.BIT_add(c)
	R = N - x - L
	a = bit.BIT_search(L - 1) if L >= 2 else 0
	b = bit.BIT_search(L) if L >= 1 else 0
	d = bit.BIT_search(L + 2) if R >= 1 else N + 1
	e = bit.BIT_search(L + 3) if R >= 1 else N + 1
	coef = 0
	if b != 0:
		coef += (b - a) * (d - c)
	if d != 0:
		coef += (e - d) * (c - b)
	ans += x * coef
print(ans)


class BIT:

	def __init__(self, N):
		self.N = N
		self.bit = [0] * (N + 1)
		self.b = 1 << N.bit_length() - 1

	def add(self, a, w):
		x = a
		while x <= self.N:
			self.bit[x] += w
			x += x & -x

	def get(self, a):
		(ret, x) = (0, a - 1)
		while x > 0:
			ret += self.bit[x]
			x -= x & -x
		return ret

	def cum(self, l, r):
		return self.get(r) - self.get(l)

	def lowerbound(self, w):
		if w <= 0:
			return 0
		x = 0
		k = self.b
		while k > 0:
			if x + k <= self.N and self.bit[x + k] < w:
				w -= self.bit[x + k]
				x += k
			k //= 2
		return x + 1
N = int(input())
P = list(map(int, input().split()))
dic = {}
bit = BIT(N)
for i in range(N):
	dic[P[i]] = i + 1
dic[0] = 0
dic[N + 1] = N + 1
ans = 0
ng = [0, N + 1]
for i in reversed(range(1, N + 1)):
	bit.add(dic[i], 1)
	c = bit.get(dic[i] + 1)
	(l1, l2) = (bit.lowerbound(c - 1), bit.lowerbound(c - 2))
	(r1, r2) = (bit.lowerbound(c + 1), bit.lowerbound(c + 2))
	S = (l1 - l2) * (r1 - dic[i]) + (r2 - r1) * (dic[i] - l1)
	ans += S * i
print(ans)


class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)

	def ope(self, x, y):
		return x + y

	def update(self, i, v):
		while i <= self.n:
			self.data[i] = self.ope(self.data[i], v)
			i += i & -i

	def query(self, i):
		ret = 0
		while 0 < i:
			ret = self.ope(self.data[i], ret)
			i &= i - 1
		return ret

	def lowerBound(self, w):
		if w <= 0:
			return 0
		(x, k) = (0, 2 ** self.n.bit_length())
		while k:
			if x + k <= self.n and self.data[x + k] < w:
				w -= self.data[x + k]
				x += k
			k >>= 1
		return x + 1
n = int(input())
p = list(map(int, input().split()))
pos = [0] * n
for (i, pi) in enumerate(p):
	pos[pi - 1] = i
bit1 = BIT(n)
bit2 = BIT(n)
ans = 0
for pi in range(n, 0, -1):
	i = pos[pi - 1]
	cur = bit1.query(i + 1)
	if cur == 0:
		left_0 = i + 1
		left_1 = 0
	else:
		tmp = bit1.lowerBound(cur)
		tmp2 = bit1.lowerBound(cur - 1)
		left_0 = i + 1 - tmp
		left_1 = tmp - tmp2
	bit1.update(i + 1, 1)
	j = n - i - 1
	cur = bit2.query(j + 1)
	if cur == 0:
		right_0 = j + 1
		right_1 = 0
	else:
		tmp = bit2.lowerBound(cur)
		tmp2 = bit2.lowerBound(cur - 1)
		right_0 = j + 1 - tmp
		right_1 = tmp - tmp2
	bit2.update(j + 1, 1)
	ans += pi * (left_0 * right_1 + left_1 * right_0)
print(ans)


from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
import random

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
ts = time.time()
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
show_flg = False

class Bit:

	def __init__(self, n):
		self.size = n
		self.m = len(bin(self.size)) - 2
		self.arr = [0] * (2 ** self.m + 1)

	def __str__(self):
		return str(self.arr)

	def add(self, i, x):
		k = 0
		while i <= self.size:
			k += 1
			self.arr[i] += x
			i += i & -i
		return

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

	def l_bound(self, w):
		if w <= 0:
			return 0
		x = 0
		k = 2 ** self.m
		while k > 0:
			if x + k < self.size and self.arr[x + k] < w:
				w -= self.arr[x + k]
				x += k
			k //= 2
		return x + 1

class Bit0(Bit):

	def add(self, j, x):
		super().add(j + 1, x)

	def l_bound(self, w):
		return max(super().l_bound(w) - 1, 0)
n = I()
a = LI()
p = [i + 1 for (i, j) in sorted(enumerate(a), key=lambda x: x[1])]
bt = Bit0(n + 2)
bt.add(0, 1)
bt.add(n + 1, 1)
ans = 0
for i in range(n - 1, -1, -1):
	c = bt.sum(p[i])
	(w, x, y, z) = [bt.l_bound(c - 1 + i) for i in range(4)]
	c = p[i]
	bt.add(p[i], 1)
	d = (i + 1) * ((x - w) * (y - c) + (c - x) * (z - y))
	ans += d
print(ans)


ans = 0
n = int(input())
p = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
	b[p[i]] = i + 1
LL = [0] + [i for i in range(n + 1)]
RR = [i for i in range(1, n + 2)] + [n + 1]
for i in range(1, n + 1):
	l1 = LL[b[i]]
	l0 = LL[l1]
	r0 = RR[b[i]]
	r1 = RR[r0]
	ans += ((l1 - l0) * (r0 - b[i]) + (r1 - r0) * (b[i] - l1)) * i
	LL[r0] = l1
	RR[l1] = r0
print(ans)


class BinaryIndexTree:

	def __init__(self, N):
		if isinstance(N, int):
			self.N = N
			self.depth = N.bit_length()
			self.tree = [0] * (N + 1)
			self.elem = [0] * (N + 1)
		elif isinstance(N, list):
			self.N = len(N)
			self.depth = self.N.bit_length()
			self.tree = [0] + N
			self.elem = [0] + N
			self._init()
		else:
			raise 'INVALID INPUT: input must be int or list'

	def _init(self):
		size = self.N + 1
		for i in range(1, self.N):
			if i + (i & -i) > size:
				continue
			self.tree[i + (i & -i)] += self.tree[i]

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

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

	def lower_bound(self, val):
		if val <= 0:
			return 0
		i = 0
		k = 1 << self.depth
		while k:
			if i + k <= self.N and self.tree[i + k] < val:
				val -= self.tree[i + k]
				i += k
			k >>= 1
		return i + 1
N = int(input())
P = list(map(int, input().split()))
p_to_i = {p: i for (i, p) in enumerate(P, start=1)}
bit = BinaryIndexTree(N)
bit.add(p_to_i[N], 1)
ans = 0
for p in range(N - 1, 0, -1):
	cnt = N - p + 1
	i = p_to_i[p]
	bit.add(i, 1)
	Bsum = bit.sum(i)
	l2 = max(0, bit.lower_bound(Bsum - 2))
	l1 = bit.lower_bound(Bsum - 1)
	r1 = bit.lower_bound(Bsum + 1)
	r2 = min(N + 1, bit.lower_bound(Bsum + 2))
	CL = (l1 - l2) * (r1 - i)
	CR = (r2 - r1) * (i - l1)
	C = CL + CR
	ans += p * C
print(ans)


N = int(input())
P = [0] + list(map(int, input().split())) + [N + 1]
ans = 0
b = [0] * (N + 2)
for i in range(N + 2):
	b[P[i]] = i
l1 = [max(0, i - 1) for i in range(N + 2)]
l2 = [max(0, i - 2) for i in range(N + 2)]
r1 = [min(N + 1, i + 1) for i in range(N + 2)]
r2 = [min(N + 1, i + 2) for i in range(N + 2)]
for i in range(N + 1):
	m = b[i]
	(x2, x1, y1, y2) = (l2[m], l1[m], r1[m], r2[m])
	hoge = i * (abs((m - x1) * (y2 - y1)) + abs((y1 - m) * (x1 - x2)))
	ans += hoge
	r1[x1] = y1
	r2[x1] = y2
	l1[y1] = x1
	l2[y1] = x2
	r1[x2] = x1
	r2[x2] = y1
	l1[y2] = y1
	l2[y2] = x1
print(ans)


import sys
input = sys.stdin.readline

def main():
	n = int(input()[:-1])
	aa = list(map(int, input().split()))
	ans = 0
	pos = [0] * (n + 1)
	for (i, a) in enumerate(aa):
		pos[a] = i + 2
	Lnext = [1, 1] + list(range(1, n + 1)) + [n, n]
	Rnext = [3, 3] + list(range(3, n + 3)) + [n + 2, n + 2]
	for a in range(1, n + 1):
		i = pos[a]
		l0 = Lnext[i]
		l1 = Lnext[l0]
		r0 = Rnext[i]
		r1 = Rnext[r0]
		ans += a * ((l0 - l1) * (r0 - i) + (i - l0) * (r1 - r0))
		Lnext[r0] = l0
		Rnext[l0] = r0
	print(ans)
main()


class BIT:

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

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

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

	def bsearch(self, x):
		i = 0
		s = 0
		step = 1 << self.n.bit_length() - 1
		while step:
			if i + step <= self.n and s + self.tree[i + step] < x:
				i += step
				s += self.tree[i]
			step >>= 1
		return i + 1
N = int(input())
P = [0] + [int(c) for c in input().split()]
ntoi = [0] * (N + 1)
for i in range(N + 1):
	ntoi[P[i]] = i
bit = BIT(N)
ans = 0
for m in range(N, 0, -1):
	I = ntoi[m]
	L = bit.bsum(I)
	bit.badd(I, 1)
	R = N - L - m
	a = bit.bsearch(L - 1) if L > 1 else 0
	b = bit.bsearch(L) if L > 0 else 0
	c = bit.bsearch(L + 2) if R > 0 else N + 1
	d = bit.bsearch(L + 3) if R > 1 else N + 1
	coef = 0
	if b != 0:
		coef += (b - a) * (c - I)
	if c != 0:
		coef += (I - b) * (d - c)
	ans += m * coef
print(ans)


(N, *P) = map(int, open(0).read().split())
idx_dict = [0] * (N + 1)
for i in range(N):
	idx_dict[P[i]] = i + 1
cnt = 0
l = [0] + [i for i in range(N + 1)]
r = [i + 1 for i in range(N + 1)] + [N + 1]
for v in range(1, N + 1):
	i = idx_dict[v]
	l1 = l[i]
	l2 = l[l1]
	r1 = r[i]
	r2 = r[r1]
	cnt += ((l1 - l2) * (r1 - i) + (i - l1) * (r2 - r1)) * v
	l[r1] = l1
	r[l1] = r1
print(cnt)