Problem:
 Score: 500 points    Problem Statement  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 1 3
2 3 1      Sample Output 1 5  X_{1, 2} = 2, X_{1, 3} = 2 , and X_{2, 3} = 1 , so the sum is 2 + 2 + 1 = 5 .       Sample Input 2 5
1 2 3 4 5      Sample Output 2 30       Sample Input 3 8
8 2 7 3 4 5 6 1      Sample Output 3 136

Solution (Python):
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(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)

Solution (Python):
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(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)

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

Solution (Python):
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


if __name__ == '__main__':
    main()

Solution (Python):
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


if __name__ == '__main__':
    main()

Solution (Python):
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


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import sys
import random
from operator import itemgetter


class RandomizedBinarySearchTree:
    def __init__(self, n):
        n += 10
        self.n = n
        self.children = [[0] * n, [0] * n]
        self.values = [0] * n
        self.counts = [0] * n
        self.indices = list(range(n - 2, -1, -1))
        self.root = -1

    def merge(self, left_root, right_root):
        children = self.children
        counts = self.counts
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if random.randrange(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[1][li]
            else:
                stack.append((ri, 0))
                ri = children[0][ri]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[is_right][pi] = i
            counts[pi] = counts[children[0][pi]] + counts[children[1][pi]] + 1
            i = pi

        return i

    def split(self, root, x):
        i = root
        children = self.children
        values = self.values
        counts = self.counts
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[0][i]
            else:
                l_stack.append(i)
                i = children[1][i]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[1][pi] = li
            counts[pi] = counts[children[0][pi]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[0][pi] = ri
            counts[pi] = counts[ri] + counts[children[1][pi]] + 1
            ri = pi

        return li, ri

    def insert(self, x):
        children = self.children
        values = self.values
        counts = self.counts

        ni = self.indices.pop()
        children[0][ni] = children[1][ni] = -1
        values[ni] = x
        counts[ni] = 1

        li, ri = self.split(self.root, x)
        self.root = self.merge(self.merge(li, ni), ri)

    def delete(self, x):
        children = self.children
        counts = self.counts
        li, mri = self.split(self.root, x - 1)
        mi, ri = self.split(mri, x)

        if mi == -1:
            self.root = self.merge(li, ri)
            return

        if counts[mi] == 1:
            self.indices.append(mi)
            self.root = self.merge(li, ri)
            return

        i = mi
        stack = []
        while i != -1:
            if children[0][i] != -1 and children[1][i] != -1:
                to_right = 1 if counts[children[0][i]] < counts[children[1][i]] else 0
                stack.append((i, to_right))
                i = children[to_right][i]
            else:
                if children[0][i] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[is_right][pi] = children[0][i]
                    else:
                        mi = children[0][i]
                elif children[1][i] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[is_right][pi] = children[1][i]
                    else:
                        mi = children[1][i]
                else:
                    pi, is_right = stack[-1]
                    children[is_right][pi] = -1
                break

        self.indices.append(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        self.root = self.merge(self.merge(li, mi), ri)

    def upper_bound(self, x, default=-1):
        i = self.root
        children = self.children
        values = self.values
        counts = self.counts
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[0][i]]
                i = children[0][i]
            else:
                j += counts[children[0][i]] + 1
                i = children[1][i]
        return y, c

    def lower_bound(self, x, default=-1):
        i = self.root
        children = self.children
        values = self.values
        counts = self.counts
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[0][i]]
                i = children[0][i]
            else:
                j += counts[children[0][i]] + 1
                i = children[1][i]
        return y, c

    def get_k_th(self, k, default=-1):
        i = self.root
        children = self.children
        values = self.values
        counts = self.counts
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[0][i]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[0][i]
            else:
                j -= left_count + 1
                i = children[1][i]
        return default

    def debug_print(self):
        print('Lefts ', self.children[0])
        print('Rights', self.children[1])
        print('Values', self.values)
        print('Counts', self.counts)
        self._debug_print(self.root, 0)

    def _debug_print(self, i, depth):
        if i != -1:
            self._debug_print(self.children[0][i], depth + 1)
            print('      ' * depth, self.values[i], self.counts[i])
            self._debug_print(self.children[1][i], depth + 1)


n = int(input())
ppp = list(map(int, input().split()))
pps = list(enumerate(ppp))
pps.sort(reverse=True, key=itemgetter(1))

rbst = RandomizedBinarySearchTree(n)
rbst.insert(-1)
rbst.insert(-1)
rbst.insert(n)
rbst.insert(n)

ans = 0
for i, p in pps:
    r1, j = rbst.upper_bound(i)
    r2 = rbst.get_k_th(j + 1)
    l1 = rbst.get_k_th(j - 1)
    l2 = rbst.get_k_th(j - 2)
    ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
    rbst.insert(i)
print(ans)

Solution (Python):
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)

Solution (Python):
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)
	
	
if __name__ == "__main__":
		main()

Solution (Python):

class BalancingTree:
    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

    def __init__(self, n):
        self.N = n
        self.root = self.node(1 << n, 1 << n)

    def debug(self):
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1,
                    nd_.right.value - 1 if nd_.right else -1)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re

        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def append(self, v):  
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p & -p) // 2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p & -p) // 2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v):  
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v):  
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    if prev == 2 ** self.N:
                        return None
                    else:
                        return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    if prev == 2 ** self.N:
                        return None
                    else:
                        return prev - 1

    @property
    def find_max(self):
        return self.find_l((1 << self.N) - 1)

    @property
    def find_min(self):
        return self.find_r(-1)

    def delete(self, v, nd=None, prev=None):  
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v


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

    A = []
    for i in range(N):
        A.append((P[i], i))

    A.sort(reverse=True)

    BT = BalancingTree(17)
    ans = 0
    for i in range(N):
        p, idx = A[i]
        BT.append(idx)

        l1 = BT.find_l(idx)  
        l2 = BT.find_l(l1)

        r1 = BT.find_r(idx)
        if r1 is None:
            r1 = N
        r2 = BT.find_r(r1)
        if r2 is None:
            r2 = N

        cmb = (l1 - l2) * (r1 - idx) + (r2 - r1) * (idx - l1)
        ans += p * cmb

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
import os
import sys

import numpy as np












def solve(inp):
    RBT_SIZE = 100010
    RBT_EOT = -2
    RBT_AVAILABLE_INDICES = set(range(RBT_SIZE - 1))
    RBT_CHILDREN = np.zeros((RBT_SIZE, 2), dtype=np.int64)
    RBT_VALUES = np.zeros(RBT_SIZE, dtype=np.int64)
    RBT_COLORS = np.zeros(RBT_SIZE, dtype=np.int64)
    RBT_COUNTS = np.zeros(RBT_SIZE, dtype=np.int64)
    RBT_ROOT = -1
    RBT_CHILDREN[RBT_ROOT, 0] = RBT_CHILDREN[RBT_ROOT, 1] = RBT_ROOT

    def _rbt_rotate(i, is_right):
        """
        Rotate node i to right if is_right=1 and left if 0.
        Return the index of new node that replaces node i.
        """
        r = is_right
        ci = RBT_CHILDREN[i, r ^ 1]
        RBT_CHILDREN[i, r ^ 1] = RBT_CHILDREN[ci, r]
        RBT_CHILDREN[ci, r] = i
        RBT_COLORS[ci] = RBT_COLORS[i]
        RBT_COLORS[i] = 1
        child_count = RBT_COUNTS[ci]
        RBT_COUNTS[ci] = RBT_COUNTS[i]
        RBT_COUNTS[i] -= child_count - RBT_COUNTS[RBT_CHILDREN[i, r ^ 1]]
        return ci

    def _rbt_balance_insert(i, is_right):
        flag = True
        r = is_right
        if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r], r ^ 1]] == 1:
            RBT_CHILDREN[i, r] = _rbt_rotate(RBT_CHILDREN[i, r], r)
        if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r], r]] == 1:
            if RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] == 1:
                RBT_COLORS[i] = 1
                RBT_COLORS[RBT_CHILDREN[i, r]] = RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] = 0
                flag = False
            else:
                i = _rbt_rotate(i, r ^ 1)
        return i, flag

    def _rbt_balance_delete(i, is_right):
        flag = True
        stack = [(i, is_right)]
        while stack:
            i, r = stack.pop()
            if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r ^ 1], r]] == 0 and \
                    RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r ^ 1], r ^ 1]] == 0:
                if RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] == 0:
                    RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] = 1
                    if RBT_COLORS[i] == 0:
                        flag = False
                    RBT_COLORS[i] = 0
                    break
                else:
                    i = _rbt_rotate(i, r)
                    stack.append((i, r))
                    stack.append((RBT_CHILDREN[i, r], r))
                    continue
            else:
                if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r ^ 1], r]] == 1:
                    RBT_CHILDREN[i, r ^ 1] = _rbt_rotate(RBT_CHILDREN[i, r ^ 1], r ^ 1)
                i = _rbt_rotate(i, r)
                RBT_COLORS[RBT_CHILDREN[i, r]] = 0
                RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] = 0
                break

        while stack:
            pi, r = stack.pop()
            RBT_CHILDREN[pi, r] = i
            i = pi

        return i, flag

    def _rbt_get_min_in_subtree(i, stack):
        while RBT_CHILDREN[i, 0] != -1:
            stack.append((i, 0))
            i = RBT_CHILDREN[i, 0]
        return i

    def rbt_insert(root, x):
        """
        Insert value x.
        Return new root index
        """

        stack = []
        i = root
        while i != -1:
            to_right = 1 if x >= RBT_VALUES[i] else 0
            stack.append((i, to_right))
            i = RBT_CHILDREN[i, to_right]

        for pi, _ in stack:
            RBT_COUNTS[pi] += 1

        i = RBT_AVAILABLE_INDICES.pop()
        RBT_CHILDREN[i, 0] = -1
        RBT_CHILDREN[i, 1] = -1
        RBT_VALUES[i] = x
        RBT_COLORS[i] = 1
        RBT_COUNTS[i] = 1

        if stack:
            pi, r = stack[-1]
            RBT_CHILDREN[pi, r] = i

        while stack:
            pi, is_right = stack.pop()
            if RBT_COLORS[pi] == 1:
                i = pi
                continue
            RBT_CHILDREN[pi, is_right] = i
            i, flag = _rbt_balance_insert(pi, is_right)

            if stack and flag:
                pi, is_right = stack.pop()
                RBT_CHILDREN[pi, is_right] = i
                break

        else:
            RBT_COLORS[i] = 0
            return i

        return root

    def rbt_delete(root, x):
        """
        Delete value x.
        Return new root index
        """
        i = root
        stack = []
        while i != -1 and RBT_VALUES[i] != x:
            is_right = 1 if RBT_VALUES[i] < x else 0
            stack.append((i, is_right))
            i = RBT_CHILDREN[i, is_right]

        if i == -1:
            return root

        if RBT_CHILDREN[i, 0] != -1 and RBT_CHILDREN[i, 1] != -1:
            stack.append((i, 1))
            mi = _rbt_get_min_in_subtree(RBT_CHILDREN[i, 1], stack)
            RBT_COLORS[i] = RBT_COLORS[mi]
            i = mi

        for pi, _ in stack:
            RBT_COUNTS[pi] -= 1

        pi, is_right = stack[-1]
        if RBT_CHILDREN[i, 0] == -1:
            RBT_CHILDREN[pi, is_right] = RBT_CHILDREN[i, 1]
            RBT_COLORS[RBT_CHILDREN[i, 1]] = 0
            if RBT_CHILDREN[i, 1] != -1 or RBT_COLORS[i] == 1:
                return root
        elif RBT_CHILDREN[i, 1] == -1:
            RBT_CHILDREN[pi, is_right] = RBT_CHILDREN[i, 0]
            RBT_COLORS[RBT_CHILDREN[i, 0]] = 0
            return root

        while stack:
            pi, is_right = stack.pop()
            i, flag = _rbt_balance_delete(pi, is_right)

            if stack and flag:
                pi, is_right = stack.pop()
                RBT_CHILDREN[pi, is_right] = i
                break

        else:
            RBT_COLORS[i] = 0
            return i

        return root

    def rbt_upper_bound(root, x):
        i = root
        y = RBT_EOT
        c = RBT_COUNTS[i]
        j = 0
        while i != -1:
            if x < RBT_VALUES[i]:
                y = RBT_VALUES[i]
                c = j + RBT_COUNTS[RBT_CHILDREN[i, 0]]
                i = RBT_CHILDREN[i, 0]
            else:
                j += RBT_COUNTS[RBT_CHILDREN[i, 0]] + 1
                i = RBT_CHILDREN[i, 1]
        return y, c

    def rbt_lower_bound(root, x):
        i = root
        y = RBT_EOT
        c = RBT_COUNTS[i]
        j = 0
        while i != -1:
            if x <= RBT_VALUES[i]:
                y = RBT_VALUES[i]
                c = j + RBT_COUNTS[RBT_CHILDREN[i, 0]]
                i = RBT_CHILDREN[i, 0]
            else:
                j += RBT_COUNTS[RBT_CHILDREN[i, 0]] + 1
                i = RBT_CHILDREN[i, 1]
        return y, c

    def rbt_get_k_th(root, k):
        i = root
        if RBT_COUNTS[i] <= k:
            return RBT_EOT
        j = k
        while i != -1:
            left_count = RBT_COUNTS[RBT_CHILDREN[i, 0]]
            if left_count == j:
                return RBT_VALUES[i]
            elif left_count > j:
                i = RBT_CHILDREN[i, 0]
            else:
                j -= left_count + 1
                i = RBT_CHILDREN[i, 1]
        return RBT_EOT

    n = inp[0]
    ppp = inp[1:]
    idx = np.argsort(ppp)[::-1]

    RBT_ROOT = rbt_insert(RBT_ROOT, -1)
    RBT_ROOT = rbt_insert(RBT_ROOT, -1)
    RBT_ROOT = rbt_insert(RBT_ROOT, n)
    RBT_ROOT = rbt_insert(RBT_ROOT, n)

    ans = 0
    for i in idx:
        p = ppp[i]
        r1, j = rbt_upper_bound(RBT_ROOT, i)
        r2 = rbt_get_k_th(RBT_ROOT, j + 1)
        l1 = rbt_get_k_th(RBT_ROOT, j - 1)
        l2 = rbt_get_k_th(RBT_ROOT, j - 2)
        ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
        RBT_ROOT = rbt_insert(RBT_ROOT, i)

    return ans


def debug_print(children, values, colors, counts, root):
    print(children.T)
    print(values)
    print(colors)
    print(counts)
    _debug_print(children, values, colors, counts, root, 0)


def _debug_print(children, values, colors, counts, i, depth):
    if i != -1:
        _debug_print(children, values, colors, counts, children[i, 0], depth + 1)
        print('      ' * depth, 'BR'[colors[i]], values[i], counts[i])
        _debug_print(children, values, colors, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)
    pass

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

Solution (Python):
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)

Solution (Python):

''' 
    [Bit]
'''
class Bit:
    """ used for only int(>=0) 
        1-indexed (ignore 0-index)
    """
    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):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        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):
        """ 累積和がx未満 の個数 """
        lb_pos, lb_sum = self.lower_bound(x)
        return lb_pos-1

    def get_less_than_and_x_cnt(self, x):
        """ 累積和がx以下 の個数 """
        lb_pos, lb_sum = self.lower_bound(x+1)
        return lb_pos-1
    
    def get_more_than_x_cnt(self, x):
        """ 累積和が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)