CodeEff/ECCO huggingface dataset:
# Original solution
import itertools

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

combi = list(itertools.combinations(list(range(n)), 2))
ans = 0

def second_max(ls):
    ls.sort()
    return ls[len(ls) - 2]

for i in range(len(combi)):
    ans += second_max(p[combi[i][0]:combi[i][1] + 1])

print(ans)

# Optimized solution
n = int(eval(input()))
p = list(map(int, input().split(' ')))
ans = 0

for i in range(n - 1):
    for j in range(i + 1, n):
        if j == i + 1:
            first_max = max(p[i], p[i + 1])
            second_max = min(p[i], p[i + 1])
        else:
            if  p[j] > first_max:
                second_max = first_max
                first_max = p[j]
            elif p[j] > second_max:
                second_max = p[j]
        ans += second_max

print(ans)
# Original solution
N = int(eval(input()))
*P, = list(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)

# Optimized solution
N = int(eval(input()))
*P, = list(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)
# Original solution
N = int(eval(input()))
P = [int(i) for i in input().split()]

ans = 0
for l in range(N-1):
    for r in range(l+1,N):
        ans += sorted(P[l:r+1])[-2]

print(ans)

# Optimized solution
N = int(eval(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)
# Original solution
n = int(eval(input()))
p = list(map(int, input().split()))
dp = [[None]*(n+1) for _ in range(n)]
ans = 0

for i in range(n-1):
    for j in range(i+1, n):
        if i+1 == j:
            a, b = p[i], p[j]
            if a > b: a ,b = b, a
            dp[i][j] = (a, b)
            ans += a
        else:
            c = p[j]
            if dp[i][j-1][0] < c:
                if dp[i][j-1][1] < c:
                    dp[i][j] = (dp[i][j-1][1], c)
                else:
                    dp[i][j] = (c, dp[i][j-1][1], c)
            else:
                dp[i][j] = dp[i][j-1]
            ans += dp[i][j][0]

print(ans)


# Optimized solution
n = int(eval(input()))
p = list(map(int, input().split()))
dp = [[None]*(n) for _ in range(n-1)]
ans = 0

for i in range(n-1):
    for j in range(i+1, n):
        if i+1 == j:
            a, b = p[i], p[j]
            if a > b: a ,b = b, a
            dp[i][j] = (a, b)
            ans += a
        else:
            c = p[j]
            if dp[i][j-1][0] < c:
                if dp[i][j-1][1] < c:
                    dp[i][j] = (dp[i][j-1][1], c)
                else:
                    dp[i][j] = (c, dp[i][j-1][1])
            else:
                dp[i][j] = dp[i][j-1]
            ans += dp[i][j][0]

print(ans)
# Original solution
import sys

def main():

	input = sys.stdin.readline

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

	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort(reverse=True)

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = ips[P[i]-1]

		larger = len(largeind)-2
		smaller = 1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		# largeind.insert(larger,target)
		largeind[larger:larger]=[target]

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

	print(x)

if __name__ == "__main__":
    main()


# Optimized solution
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)

if __name__ == "__main__":
    main()
# Original solution
import sys
from bisect import *

input=sys.stdin.readline

def main():
    n = int(input()[:-1])
    aa = list(map(int, input().split()))
    ans = 0
    pos = [0] * n
    for i, a in enumerate(aa):
        pos[a - 1] = i
    # print(pos)
    fin = [-1, -1, n, n]
    for a in range(n - 1, -1, -1):
        i = pos[a]
        insort(fin,i)
        j = bisect_left(fin, i)
        ans += (a + 1) * ((fin[j - 1] - fin[j - 2]) * (fin[j + 1] - fin[j])
                          + (fin[j] - fin[j - 1]) * (fin[j + 2] - fin[j + 1]))
        # print(a, ans, fin)
    print(ans)

main()


# Optimized solution
# 参考 https://atcoder.jp/contests/abc140/submissions/7411285
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()
# Original solution
def main():
    import sys
    input = sys.stdin.readline
    import bisect 
    n = int(eval(input()))
    l = list(map(int,input().split()))
    l1 = [0]*n
    for i in range(n):
        l1[l[i]-1] = i
    ans = 0
    s = [-1,-1,l1[-1],n,n]

    for i in range(n-2,-1,-1):
        c = l1[i]
        now = bisect.bisect_right(s,c)
        a = s[now-2]
        b = s[now-1]
        d = s[now]
        e = s[now+1]
        count = (b-a)*(d-c) + (e-d)*(c-b)
        s.insert(now,c)
        ans += count*(i+1)
    print(ans)
if __name__ == "__main__":
    main()

# Optimized solution
n=int(eval(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)
# Original solution
import bisect
N = int(eval(input()))
P = []
for i, p in enumerate(map(int, input().split())):
    P.append([p, i])

P = sorted(P, reverse = True)
    
A = [- 1, - 1, P[0][1], N, N] 

res = 0
for p, i in P[1:]:
    j = bisect.bisect_left(A, i)
    A.insert(j, i)
    res += p*((A[j] - A[j - 1])*(A[j + 2] - A[j + 1]) + (A[j - 1] - A[j - 2])*(A[j + 1] - A[j]))

print(res)

# Optimized solution
import bisect
import array
N = int(eval(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)
# Original solution
import bisect
import array
N = int(eval(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)

# Optimized solution
N = int(eval(input()))
P_id = [0]*(N + 1) # P_id[i]は順列Pに置けるiのindex, P[0]は無視
for index, p in enumerate(map(int, input().split())):
    P_id[p] = index

left_next_index = list(range(- 1, N - 1)) + ['うんこ', - 1] # + [- 1]ではないことに注意, left_next_index[r1] = l1においてr1 = Nの場合があるから
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)
# Original solution
N = int(eval(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)


# Optimized solution
N = int(eval(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
    if l>=0:
        l = L[l]
    r = idx+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-idx)
    if r<N:
        r2 = r+1
        if r2<N:
            r2 = R[r2]
        ans += n * (idx-l) * (r2-r)
print(ans)
# Original solution
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(eval(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)

# Optimized solution
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(eval(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)
# Original solution
import heapq

n = int(eval(input()))
li = [-1 * int(i) for i in input().split()]
ans = 0

for a in range(len(li)):
  li2 = li[a:]
  for b in range(len(li2)):
    li3 = li2[:b+1]
    li4 = heapq.heapify(li3)
    if len(li3) >= 2:
      heapq.heappop(li3)
      ans += ((-1)*heapq.heappop(li3))

print(ans)

# Optimized solution
n = int(eval(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)
# Original solution
N = int(eval(input()))
P = [int(i) for i in input().split(" ")]

ans = 0
for L in range(N-1):
    for R in range(L+1, N):
        if 2 <= len(P[L:R+1]) <= 3:
            seq = sorted(P[L:R+1], reverse=True)
        else:
            if seq[0] > P[R] > seq[1]:
                seq = [seq[0], P[R], seq[1]]
            elif P[R] > seq[0]:
                seq = [P[R], seq[0], seq[1]]
            elif seq[1] > P[R] > seq[2]:
                seq = [seq[0], seq[1], P[R]]
        ans += seq[1]
print(ans)

# Optimized solution
N = int(eval(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]

# 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)
# Original solution
from bisect import bisect_left
import sys

input = sys.stdin.readline

n = int(eval(input()))
p = tuple(map(int, input().split()))

pos = [[] for _ in range(n + 1)]
for ind, pp in enumerate(p):
    for j in range(pp + 1):
        pos[j].append(ind)

ans = 0
for i, pp in enumerate(p):
    ind = bisect_left(pos[pp], i)

    left = 1
    if ind - 1 >= 0:
        left = i - pos[pp][ind - 1]
    else:
        left = i + 1
    right = 0
    if ind + 1 < len(pos[pp]):
        i_right = pos[pp][ind + 1]
        right = 1
        if ind + 2 < len(pos[pp]):
            right = pos[pp][ind + 2] - i_right
        else:
            right = n - i_right

    # print(i, pp, left * right, left, right)
    ans += left * right * pp

    left = 0
    if ind - 1 >= 0:
        i_left = pos[pp][ind - 1]
        left = 1
        if ind - 2 >= 0:
            left = i_left - pos[pp][ind - 2]
        else:
            left = i_left + 1
    right = 1
    if ind + 1 < len(pos[pp]):
        right = pos[pp][ind + 1] - i
    else:
        right = n - i

    # print(i, pp, left * right, left, right)
    ans += left * right * pp

print(ans)


# Optimized solution
# https://atcoder.jp/contests/abc140/submissions/7411285
# 写経

def main():
    N = int(eval(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):
        # l2, ..., l1, ..., x, ..., r1, ..., r2
        # (l2,r1) or (l1,r2)
        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)


if __name__ == '__main__':
    main()
# Original solution
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 [1 << x for x in 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
        return self.func(self.table[log][i], self.table[log][j - length])


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


n = int(eval(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, p[i])
    ans += p[i] * ((i-j) * (m-l) + (j-k) * (l-i))
print(ans)


# Optimized solution
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 [1 << x for x in 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(eval(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)
# Original solution
import bisect
n = int(eval(input()))
p = list(map(int, input().split()))

index = [0] * (n+1)

for i in range(n):
    index[p[i]] = i

poss = []
result = 0
for i in range(1, n+1)[::-1]:
    x = index[i]
    if len(poss) == 0:
        poss.append(x)
        continue
    dx = bisect.bisect_left(poss, x)
    # 左に１番目の数がある
    if dx > 0:
        lbl = 0
        if dx > 1:
            lbl = poss[dx-2]+1
        lbr = poss[dx-1]
        rbl = n-1
        if len(poss) != dx:
            rbl = poss[dx] -1
        result += (lbr-lbl+1) * (rbl-x+1) * i
    # 右に1番目の数がある
    if dx < len(poss):
        rbr = n-1
        if dx < len(poss) -1:
            rbr = poss[dx+1]-1
        rbl = poss[dx]
        lbr = 0
        if dx > 0:
            lbr = poss[dx-1] +1
        result += (rbr-rbl+1) * (x-lbr+1) * i
    poss.insert(dx, x)

print(result)

# Optimized solution
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(eval(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
    # 右に1番目の数がある
    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)
# Original solution
N = int(eval(input()))
ls = [int(i) for i in input().split()]
#N = 5
#ls = [1,2,3,4,5]

dic = {}
result = []

def get_second_large(ls):
  if len(ls) < 2:
    return ls[0]
  else:
    return sorted(ls)[-2]


for l in range(N):
    for r in range(l+1,N):
      tup = tuple(ls[l:r+1])
      if tup not in dic:
        second = get_second_large(ls[l:r+1])
        dic[tup] = second
      result.append(dic[tup])
print((sum(result)))

# Optimized solution
N = int(eval(input()))
ls = [int(i) for i in input().split()]
result = []


for l in range(N-1):
    if ls[l] > ls[l+1]:
        sec_big, biggist = ls[l+1], ls[l]
    else:
        sec_big, biggist = ls[l], ls[l+1]
    result.append(sec_big)
    for r in range(l+2, N):
        if ls[r] > biggist:
            result.append(biggist)
            sec_big = biggist
            biggist = ls[r]
        elif biggist > ls[r] > sec_big:
            result.append(ls[r])
            sec_big = ls[r]
        else:
            result.append(sec_big)
print((sum(result)))
# Original solution
#!/usr/bin/env python3
N=int(eval(input()))
p=list(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:
  r0 = RR[i]
  r1 = RR[r0]
  l0 = LL[i]
  l1 = LL[l0]
  RR[l0] = r0
  LL[r0] = l0

  ans += ((r1 - r0)*(i-l0)+(r0-i)*(l0 - l1))*v

print(ans)


# Optimized solution
#!/usr/bin/env python3
ans=0
n=int(eval(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)