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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def getSize(self, x):
        return self.size[self.find(x)]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
A = [0] + list(map(int, input().split())) + [N+1]
B = [None] * (N+2)
for i, x in enumerate(A):
    B[x] = i
A[0] = N+1
uf = UnionFind(N+1)
ans = 0
for x in range(1, N):
    i = B[x]
    if A[i-1] < A[i]:
        uf.unite(i-1, i)
    if A[i] > A[i+1]:
        uf.unite(i, i+1)
    if x < A[i-1]:
        k2 = i-1
    else:
        l, r = 0, i-1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(m, i-1):
                r = m
            else:
                l = m
        k2 = l
    if k2 == 0 or A[max(0, k2-1)] > x:
        k1 = max(0, k2-1)
    else:
        l, r = 0, k2-1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(m, k2-1):
                r = m
            else:
                l = m
        k1 = l
    if x < A[i+1]:
        k3 = i+1
    else:
        l, r = i+1, N+1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(i+1, m):
                l = m
            else:
                r = m
        k3 = r
    if k3 == N+1 or x < A[min(N+1, k3+1)]:
        k4 = min(N+1, k3+1)
    else:
        l, r = k3+1, N+1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(k3+1, m):
                l = m
            else:
                r = m
        k4 = r
    ans += x * ((k2-k1)*(k3-i) + (k4-k3)*(i-k2))
print(ans)

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

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

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

Solution (Python):
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):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        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):
    """
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= 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)

Solution (Python):

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)

if __name__ == '__main__':
    main()

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

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
class PMS:
    
    def __init__(self, A, B, issum = False):
        
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        if issum:
            self.sumtree = [0] * (self.size + 1)
            Ssum = [0] + list(accumulate([CA[self.X[i]]*self.X[i] for i in range(self.size)]))
            for i in range(1, 1+self.size):
                self.sumtree[i] = Ssum[i] - Ssum[i - (i&-i)]
    
    def compress(self, L):
        
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        
        return L2, C
    
    def leng(self):
        
        return self.count(self.X[-1])
    
    def count(self, v):
        
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, v, x):
        
        i = self.comp[v]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def get(self, i):
        
        if i <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < i:
                s += k
                i -= self.tree[s]
            k //= 2
        return self.X[s]
    
    def gets(self, v):
        
        v1 = v
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.sumtree[s+k] < v:
                s += k
                v -= self.sumtree[s]
            k //= 2
        if s == self.size:
            return self.leng()
        return self.count(self.X[s]) + (v1 - self.countsum(self.X[s]))//self.X[s]
    
    def addsum(self, i, x):
        
        self.add(i, x)
        x *= i
        i = self.comp[i]
        while i <= self.size:
            self.sumtree[i] += x
            i += i & -i
    
    def countsum(self, v):
        
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.sumtree[i]
            i -= i & -i
        return s
    
    def getsum(self, i):
        
        x = self.get(i)
        return self.countsum(x) - x*(self.count(x) - i)




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

T = PMS([0, 0, N+1, N+1], list(range(-1, N+3)))

K = [None]*(N+4)
K[-1] = 0
K[0] = 0
K[N+1] = N+1
K[N+2] = N+1

for i in range(N):
    p = P[i]
    K[p] = i+1

ans = 0

for j in range(N, 0, -1):
    k = K[j]
    T.add(k, 1)
    cnt = T.count(k)
    a = T.get(cnt-2)
    b = T.get(cnt-1)
    c = k
    d = T.get(cnt+1)
    e = T.get(cnt+2)
    ans += j*((e-d)*(c-b) + (d-c)*(b-a))

print(ans)

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