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











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)

if __name__ == '__main__':
    main()

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

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

Solution (Python):



def main():
    N = int(input())
    *p, = 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)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

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

def main():
    mod=10**9+7
    N=I()
    P=LI()
    
    
    

    
    def segfunc1(x,y):
        
        return max(x,y)

    
    def update1(k,x):
        k += num-1
        seg1[k] = x
        while k:
            k = (k-1)//2
            seg1[k] = segfunc1(seg1[k*2+1],seg1[k*2+2])

            
    
    def query1(p,q):
        if q<=p:
            return ide_ele1
        p += num-1
        q += num-2
        res=ide_ele1
        while q-p>1:
            if p&1 == 0:
                res = segfunc1(res,seg1[p])
            if q&1 == 1:
                res = segfunc1(res,seg1[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc1(res,seg1[p])
        else:
            res = segfunc1(segfunc1(res,seg1[p]),seg1[q])
        return res
    
    
    
    
    def segfunc2(x,y):
        
        return min(x,y)

    
    def update2(k,x):
        k += num-1
        seg2[k] = x
        while k:
            k = (k-1)//2
            seg2[k] = segfunc2(seg2[k*2+1],seg2[k*2+2])

            
    
    def query2(p,q):
        if q<=p:
            return ide_ele2
        p += num-1
        q += num-2
        res=ide_ele2
        while q-p>1:
            if p&1 == 0:
                res = segfunc2(res,seg2[p])
            if q&1 == 1:
                res = segfunc2(res,seg2[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc2(res,seg2[p])
        else:
            res = segfunc2(segfunc2(res,seg2[p]),seg2[q])
        return res

    
    ide_ele1 = 0
    ide_ele2 = 10**10



    
    num =2**(N+1).bit_length()
    seg1=[ide_ele1]*2*num
    seg2=[ide_ele2]*2*num
    
    
    
    
    px=[[0,0]for _ in range(N)]
    for x in range(N):
        px[x]=[P[x],x+1]
    px.sort(reverse=True)
    
    a=[0]*(N+2)
    b=[0]*(N+2)
    c=[0]*(N+2)
    d=[0]*(N+2)

    
    update2(N+1,N+1)
    
    for i in range(N):
        p=px[i][0]
        x=px[i][1]
        update1(x,x)
        update2(x,x)
        b[x]=query1(0,x)
        c[x]=query2(x+1,N+2)
        if b[x]<=0:
            a[x]=0
        else:
            a[x]=query1(0,b[x])
            
        if c[x]>=N+1:
            d[x]=N+1
        else:
            d[x]=query2(c[x]+1,N+2)
            
    ans=0
    
    
    for i in range(1,N+1):
        if b[i]!=0:
            cnt=(b[i]-a[i])*(c[i]-i)
            ans+=cnt*P[i-1]
        if c[i]!=(N+1):
            cnt=(i-b[i])*(d[i]-c[i])
            ans+=cnt*P[i-1]
            
    print(ans)
            
    
    

main()

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

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

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

if __name__ == '__main__':
    examE()

"""

"""

Solution (Python):
class BinaryIndexTree:  
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        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


if __name__ == "__main__":
    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)

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

Solution (Python):
n=int(input())
p=list(map(int,input().split()))
ind=[0]*n
for i in range(n):ind[p[i]-1]=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(n):
  ans+=(r[r[ind[i]]]-r[ind[i]])*(ind[i]-l[ind[i]])*(i+1)
  ans+=(l[ind[i]]-l[l[ind[i]]])*(r[ind[i]]-ind[i])*(i+1)
  l[r[ind[i]]],r[l[ind[i]]]=l[ind[i]],r[ind[i]]
print(ans)

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

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

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


if __name__ == '__main__':
    solve()

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

Solution (Python):





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)

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

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

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

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

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

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