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):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    class BIT():
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
    
    N=int(input())
    P=list(map(int,input().split()))
    P2=[(P[i],i) for i in range(N)]
    P2.sort(reverse=True)
    b=BIT(N)
    
    def nibutan(i,num,ok,ng):
        b_sum_i=b.sum(i)
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(b_sum_i,i,num,mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(b_sum_i,i,num,mid):
        if i>mid:
            if b_sum_i-b.sum(mid-1) >= num:
                return True
        else:
            if b.sum(mid)-b_sum_i >= num:
                return True
        return False
    
    ans=0
    for p in P2:
        x=b.sum(p[1])
        y=b.sum(N-1)
        if x>=1 or y-x>=1:
            s=nibutan(p[1],1,-1,p[1])
            t=nibutan(p[1],2,-1,p[1])
            u=nibutan(p[1],1,N,p[1])
            v=nibutan(p[1],2,N,p[1])
            if x>=1:
                ans+=p[0]*(s-t)*(u-p[1]) if s>-1 else 0
            if y-x>=1:
                ans+=p[0]*(v-u)*(p[1]-s) if u<N else 0
        b.add(p[1],1)
    
    print(ans)
    

if __name__ == '__main__':
    main()

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


def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()

def main():
    N = ri()
    P = [N+1,N+1] + ria() + [N+1,N+1]

    ord = []
    for i in range(2,N+2):
        ord.append((P[i], i))

    ord = sorted(ord) 

    
    
    
    
    tot = 0
    l = [i for i in range(N + 4)]
    r = [i for i in range(N + 4)]
    used = [False] * (N + 4)
    for v, idx in ord:
        
        used[idx] = True
        if used[idx - 1]:
            l[idx] = l[idx - 1]
        if used[idx + 1]:
            r[idx] = r[idx + 1]
        r[l[idx]] = r[idx]
        l[r[idx]] = l[idx]

        l0 = l[idx] - 1
        r0 = r[idx] + 1
        l1 = l0 - 1 if not used[l0 - 1] else (l[l0-1] - 1)
        r1 = r0 + 1 if not used[r0 + 1] else (r[r0+1] + 1)
        

        if l1 != 0:
            rseg = r0 - idx
            lseg = l0 - l1
            tot += lseg * rseg * v
        if r1 != N + 3:
            rseg = r1 - r0
            lseg = idx - l0
            tot += lseg * rseg * v

    print(tot)




if __name__ == "__main__":
    main()

Solution (Python):
import heapq
from collections import defaultdict
N = int(input())
P = list(map(int,input().split()))

d_r = defaultdict(lambda:N+1)
h_r = []
d_r2 = defaultdict(lambda:N+1)
h_r2 = []
for i in range(N):
    p = P[i]
    while h_r2:
        q = heapq.heappop(h_r2)
        if q < p:
            d_r2[q] = p
        else:
            heapq.heappush(h_r2,q)
            break
    while h_r:
        q = heapq.heappop(h_r)
        if q < p:
            d_r[q] = p
            heapq.heappush(h_r2,q)
        else:
            heapq.heappush(h_r,q)
            break
    heapq.heappush(h_r,p)


d_l = defaultdict(lambda:0)
h_l = []
d_l2 = defaultdict(lambda:0)
h_l2 = []
for i in range(N-1,-1,-1):
    p = P[i]
    while h_l2:
        q = heapq.heappop(h_l2)
        if q < p:
            d_l2[q] = p
        else:
            heapq.heappush(h_l2,q)
            break
    while h_l:
        q = heapq.heappop(h_l)
        if q < p:
            d_l[q] = p
            heapq.heappush(h_l2,q)
        else:
            heapq.heappush(h_l,q)
            break
    heapq.heappush(h_l,p)

d = {}
for i in range(N):
    d[P[i]] = i
d[N+1] = N
d[0] = -1
ans = 0
for i in range(N):
    x = d[d_l2[P[i]]]
    y = d[d_l[P[i]]]
    z = d[d_r[P[i]]]
    w = d[d_r2[P[i]]]
    ans += P[i]*((y-x)*(z-i)+(w-z)*(i-y))
print(ans)

Solution (Python):
n = int(input())
P = list(map(int, input().split()))

num_idx = [0]*(n+1)


right_idx_over_current_pos = list(range(1, n+1)) + [n, n]

left_idx_over_current_pos = list(range(-1, n-1)) + [-1, -1]



for idx, num in enumerate(P):
    num_idx[num] = idx

ans = 0
for num in range(1, n+1):  
    now = num_idx[num]
    r1 = right_idx_over_current_pos[now]
    r2 = right_idx_over_current_pos[r1]
    l1 = left_idx_over_current_pos[now]
    l2 = left_idx_over_current_pos[l1]

    r_pattern = (r2-r1) * (now-l1)
    l_pattern = (l1-l2) * (r1-now)

    right_idx_over_current_pos[l1] = r1  
    left_idx_over_current_pos[r1] = l1  
    ans += (r_pattern + l_pattern) * num

print(ans)

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

print(ans)

Solution (Python):
from random import random, sample


def bis_l(a, k):
  l = 0
  r = len(a)
  while l != r:
    m = (l + r) >> 1
    if a[m] < k:
      l = m + 1
    else:
      r = m
  return l


def bis_r(a, k):
  l = 0
  r = len(a)
  while l != r:
    m = (l + r) >> 1
    if a[m] <= k:
      l = m + 1
    else:
      r = m
  return l


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

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

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

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

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

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

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


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


main()

Solution (Python):

from bisect import bisect_left, bisect_right
from random import random, sample


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

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

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

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

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

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

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


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


main()

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

pos_list = [0] * n

for index, i in enumerate(p, 0):
    
    pos_list[i - 1] = index
    

left_next_index = list(range(-1, n-1)) + [-1, -1]
right_next_index = list(range(1, n+1)) + [n, n]

answer = 0


for i in range(1, n):
    index = pos_list[i-1]
    l1 = left_next_index[index]
    l2 = left_next_index[l1]
    r1 = right_next_index[index]
    r2 = right_next_index[r1]
    
    answer += i * ((index-l1) * (r2-r1) + (r1-index) * (l1-l2))

    left_next_index[r1] = l1
    right_next_index[l1] = r1

print(answer)

Solution (Python):
def main():
    class unionfind():
        
        def __init__(self,size):
            self.size=size
            self.tree=[i for i in range(self.size)]
        
        
        def root(self,index):
            temp_list=[]
            temp=self.tree[index]
            while index!=temp:
                temp_list.append(index)
                index=temp
                temp=self.tree[index]
            for i in temp_list:
                self.tree[i]=index
            return index
        
        
        def unite_r(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1<r2:
                self.tree[r1]=r2
            else:
                self.tree[r2]=r1

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

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

Solution (Python):
def main():
    class unionfind():
        
        def __init__(self,size):
            self.size=size
            self.tree=[i for i in range(self.size)]
        
        
        def root(self,index):
            temp_list=[]
            temp=self.tree[index]
            while index!=temp:
                temp_list.append(index)
                index=temp
                temp=self.tree[index]
            for i in temp_list:
                self.tree[i]=index
            return index
        
        
        def unite_r(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1<r2:
                self.tree[r1]=r2
            else:
                self.tree[r2]=r1

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

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

Solution (Python):

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


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

"""
大きい数から挿入していく
左隣にあるインデックスを取得できるようにしておく
そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ
"""


tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    
    L = BIT_sum(c)
    
    R = BIT_sum(N) - L
    
    BIT_add(c)
    
    a = BIT_search(L-1) if L > 1 else 0
    b = BIT_search(L) if L > 0 else 0
    
    d = BIT_search(L+2) if R > 0 else N+1
    e = 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)
    answer += x * coef

print(answer)

Solution (Python):

class BITbisect():
    def __init__(self, max):
        self.max = max
        self.data = [0]*(self.max+1)
    
    
    
    def query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

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

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

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

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

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

    
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max+1):
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
bit = BITbisect(N)

co_to_ind = [0]*(N+1)
for i in range(N):
    co_to_ind[A[i]] = i+1
    bit.insert(i+1)

ans = 0
for n in range(1, N+1):
    ind = co_to_ind[n]
    seq = bit.bisect_left(ind)
    L = bit.length()
    if seq >= 2:
        l1 = bit.search(seq-1)
        l0 = bit.search(seq-2)
    elif seq == 1:
        l1 = bit.search(seq-1)
        l0 = 0
    else:
        l1 = 0
        l0 = 0
    if L-1 - seq >= 2:
        r1 = bit.search(seq+1)
        r0 = bit.search(seq+2)
    elif L-1 - seq == 1:
        r1 = bit.search(seq+1)
        r0 = N+1
    else:
        r1 = N+1
        r0 = N+1
    
    ans += ((ind-l1)*(r0-r1) + (l1-l0)*(r1-ind)) * n
    bit.delete(ind)

print(ans)

Solution (Python):
N = int(input())
P = [None] + list(map(int, input().split()))

p_to_index = [None] * (N + 1)
for index, x in enumerate(P[1:], 1):
    p_to_index[x] = index


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

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

def BIT_search(x):
    i = 0
    s = 0
    step = 1 << (len(bin(N)[2:]) - 1)
    while step:
        if i + step <= N and s + tree[i + step] < x:
            i += step
            s += tree[i]
        step >>= 1
    return i + 1

tree = [0] * (N + 1)
ans = 0
for x in range(N, 0, -1):
    c = p_to_index[x]
    L = BIT_sum(c)
    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 + 1) if R >= 1 else N + 1
    e = BIT_search(L + 2) if R >= 2 else N + 1
    BIT_add(c)
    tmp = 0
    if b != 0:
        tmp += (b - a) * (d - c)
    if d != 0:
        tmp += (e - d) * (c - b)
    ans += tmp * x

print (ans)

Solution (Python):
class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

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

    def query(self, l, r):  
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


N = int(input())
P = [int(_) for _ in input().split()]
p_i = {p: i + 1 for i, p in enumerate(P)}
SL = SegmentTree([0] * (N + 2), max, 0)
SR = SegmentTree([N + 1] * (N + 2), min, N + 1)
ans = 0
for p in range(N, 0, -1):
    i = p_i[p]
    SL.update(i, i)
    SR.update(i, i)
    il = SL.query(0, i)
    ir = SR.query(i + 1, N + 2)
    if il > 0:
        ill = SL.query(0, il)
        ans += p * (il - ill) * (ir - i)
    if ir < N + 1:
        irr = SR.query(ir + 1, N + 2)
        ans += p * (irr - ir) * (i - il)
print(ans)

Solution (Python):
from time import time
from statistics import median
from bisect import bisect_left, bisect_right
from random import random, sample


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

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

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

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

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

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

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


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


main()

Solution (Python):
from time import time
from statistics import median
from bisect import bisect_left, bisect_right
from random import random, sample


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

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

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

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

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

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

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


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


main()