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



Sample input:
3
2 3 1


Sample output:
5

Submission status: Wrong Answer

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

##  input functions for me
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) # P[i], i , P[i]順でソート

    # ..AsssBssCssDsssE.. のようになっている（Cが自分 A,B,D,E>C，s<C）
    # CからA,B,D,Eのインデクスを知りたいので，Cより小さい区間は連結にして置き，
    # スキップできるように各連結成分の両端に情報を乗せておく
    #  union-findで管理してもいいが，アクセスする場所と回数が限られているので配列で管理できる
    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ならマージする
        used[idx] = True
        if used[idx - 1]:
            l[idx] = l[idx - 1]
            r[l[idx]] = idx
        if used[idx + 1]:
            r[idx] = r[idx + 1]
            l[r[idx]] = 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()

Submission status: Wrong Answer

Solution code:
def main():
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[i for i in range(self.size)]#root,depth
        
        #rootを探す
        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)
            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_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()

Submission status: Wrong Answer

Solution code:
def main():
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[i for i in range(self.size)]#root,depth
        
        #rootを探す
        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)
            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_l.unite_l(i,i-1)
            k2=u_r.root(i-1)-1
        else:
            k2=i-1
        if vis[k2-1]==True:
            cnt2=u_r.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()

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    a=list(map(int,input().split()))


    class segtree():
        def __init__(self,base,monoid,ini):#self,モノイド,元の配列
            #ini：上限（下限）,base：元の配列,monoid：モノイド,tree：セグ木,depth：treeの深さ,
            #basesize：baseの要素数,treesize：treeの要素数,num：treesize-basesize
            
            # 初期値（上限とか下限）を決定
            self.ini=ini
            #セグ木の要素数（num）および深さ（depth）を計算
            self.base=base
            self.basesize=len(self.base)
            self.num,self.depth=1,1
            while self.num<self.basesize:
                self.num*=2
                self.depth+=1
            self.num-=1
            #関数（モノイド、今回はmin）を設定
            self.monoid=monoid
            #セグ木を構築
            self.treesize=self.num*2+1
            self.tree=[None]*self.treesize
            #segtree[m]以降に代入したい配列を入力していく
            for i in range(self.num, self.num+self.basesize):self.tree[i]=self.base[i-self.num]
            for i in range(self.num+self.basesize, self.treesize):self.tree[i]=self.ini
            #segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
            for i in range(self.num-1,-1,-1):
                j=2*i+1
                self.tree[i]=self.monoid(self.tree[j],self.tree[min(j+1,self.treesize-1)])
        
        #条件を満たす(サンプルの条件はs以下になること)最大のインデックスを返す関数
        def max_index(self,index_func):
            #探していく
            i=0
            while i<self.num:
                k=2*i+1
                if k+1<self.treesize:
                    if index_func(self.tree[k+1]):
                        i=k+1
                        continue
                if k<self.treesize:
                    if index_func(self.tree[k]):
                        i=k
                        continue
                return -1
            return i-self.num
    
        #条件を満たす(サンプルの条件はs以下になること)最小のインデックスを返す関数
        def min_index(self,index_func):
            #探していく
            i=0
            while i<self.num:
                k=2*i+1
                if k<self.treesize:
                    if index_func(self.tree[k]):
                        i=k
                        continue
                if k+1<self.treesize:
                    if index_func(self.tree[k+1]):
                        i=k+1
                        continue
                return -1
            return i-self.num
    
        #半開区間[lower,upper)の最小値（とか）を探す関数
        def search(self,lower, upper):
            #返り値を初期化
            ret=self.ini
            l=lower+self.num
            r=upper+self.num
            while l<r:
                if r&1:
                    r-=1
                    ret=self.monoid(ret,self.tree[r-1])
                if l&1:
                    ret=self.monoid(ret,self.tree[l-1])
                    l+=1
                l>>=1;r>>=1
            return ret
    
        #base[i]をsに更新したときにセグ木全体を更新する関数
        def update(self,index,new_value):
            i=index+self.num
            self.tree[i]=new_value
            temp=new_value
            while i!=0:
                k=(i-1)//2
                if i%2==1:
                    temp=self.monoid(self.tree[min(i+1,self.treesize-1)],temp)
                else:
                    temp=self.monoid(self.tree[i-1],temp)
                if self.tree[k]!=temp:
                    self.tree[k]=temp
                    i=k
                    continue
                break
    
    s=segtree([10**6,10**6]+a+[10**6+10**6],max,0)

    def b_search_u(a,b,border):
        ini=a
        while True:
            med=(a+b)//2
            if a==b:return a
            if a+1==b:
                if s.search(ini,a+1)>border:return a
                else:return b
            elif s.search(ini,med+1)>border:b=med
            else:a=med+1

    def b_search_d(a,b,border):
        ini=b
        while True:
            med=(a+b)//2
            if a==b:return a
            elif a+1==b:
                if s.search(b,ini+1)>border:return b
                else:return a
            elif s.search(med,ini+1)>border:a=med
            else:b=med-1

    d=[0]*n
    for i in range(n):
        d[a[i]-1]=i
    ans=0
    for i in range(n-1):
        k1=b_search_u(d[i]+3,n+3,i+1)
        cnt1=min(b_search_u(k1+1,n+4,i+1),n+2)
        k2=b_search_d(1,d[i]+1,i+1)
        cnt2=max(b_search_d(0,k2-1,i+1),1)
        ans+=((k2-cnt2)*(k1-d[i]-2)+(cnt1-k1)*(d[i]-k2+2))*(i+1)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    a=list(map(int,input().split()))

    class segtree():
        def __init__(self,base,monoid,ini):#self,モノイド,元の配列
            #ini：上限（下限）,base：元の配列,monoid：モノイド,tree：セグ木,depth：treeの深さ,
            #basesize：baseの要素数,treesize：treeの要素数,num：treesize-basesize
            
            # 初期値（上限とか下限）を決定
            self.ini=ini
            #セグ木の要素数（num）および深さ（depth）を計算
            self.base=base
            self.basesize=len(self.base)
            self.num,self.depth=1,1
            while self.num<self.basesize:
                self.num*=2
                self.depth+=1
            self.num-=1
            #関数（モノイド、今回はmin）を設定
            self.monoid=monoid
            #セグ木を構築
            self.treesize=self.num+self.basesize
            self.tree=[None]*self.treesize
            #segtree[m]以降に代入したい配列を入力していく
            for i in range(self.num, self.treesize):self.tree[i]=self.base[i-self.num]
            #segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
            for i in range(self.num-1,-1,-1):
                j=2*i+1
                if j>=self.treesize:self.tree[i]=self.ini
                else:self.tree[i]=self.monoid(self.tree[j],self.tree[min(j+1,self.treesize-1)])
    
        #半開区間[lower,upper)の最小値（とか）を探す関数
        def search(self,lower, upper):
            q=[[0,1]]  #インデックス、階層
            #返り値を初期化
            ret=self.ini
            while q:
                i,f=q.pop()
                #popしたインデックスと階層から、求める下限と上限を算出する
                #幅
                width=pow(2,self.depth-f)
                #下限と中央と上限
                kagen=(i-pow(2,f-1)+1)*width
                chuo=kagen+width//2
                jogen=kagen+width
                k=2*i+1
                if lower<=kagen and jogen<=upper:
                    ret=self.monoid(ret,self.tree[i])
                    continue
                if k<self.treesize:
                    if lower<=kagen and chuo<=upper:ret=self.monoid(ret,self.tree[k])
                    elif lower<=chuo:q.append([k,f+1])
                if k+1<self.treesize:
                    if lower<=chuo and jogen<=upper:ret=self.monoid(ret,self.tree[k+1])
                    elif chuo<=upper:q.append([k+1,f+1])
            return ret
        
    s=segtree([10**6,10**6]+a+[10**6+10**6],max,0)

    d=[0]*n
    for i in range(n):
        d[a[i]-1]=i
    ans=0
    for i in range(1,n):
        j=d[i-1]
        aa=j+3
        b=n+3
        ini=aa
        while True:
            med=(aa+b)//2
            if aa==b:return aa
            if aa+1==b:
                if s.search(ini,aa+1)>i:
                    k1=aa
                    break
                else:
                    k1=b
                    break
            elif s.search(ini,med+1)>i:b=med
            else:aa=med+1

        aa=k1+1
        b=n+4
        ini=aa
        while True:
            med=(aa+b)//2
            if aa==b:return aa
            if aa+1==b:
                if s.search(ini,aa+1)>i:
                    cnt1=min(aa,n+2)-k1
                    break
                else:
                    cnt1=min(b,n+2)-k1
                    break
            elif s.search(ini,med+1)>i:b=med
            else:aa=med+1

        aa=1
        b=j+1
        ini=b
        while True:
            med=(aa+b)//2
            if aa==b:
                k2=aa
                break
            elif aa+1==b:
                if s.search(b,ini+1)>i:
                    k2=b
                    break
                else:
                    k2=aa
                    break
            elif s.search(med,ini+1)>i:aa=med
            else:b=med-1

        aa=0
        b=k2-1
        ini=b
        while True:
            med=(aa+b)//2
            if aa==b:
                cnt2=k2-max(aa,1)
                break
            elif aa+1==b:
                if s.search(b,ini+1)>i:
                    cnt2=k2-max(b,1)
                    break
                else:
                    cnt2=k2-max(aa,1)
                    break
            elif s.search(med,ini+1)>i:aa=med
            else:b=med-1
        ans+=(cnt2*(k1-j-2)+cnt1*(j-k2+2))*i
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
P = list(map(int, input().split()))
res = 0
P.sort()
for i in range(N - 1):
    res += (i + 1) * P[i]

print(res)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,*P = map(int,read().split())

INF = N+100
P = [INF,INF] + P + [INF,INF]

x_to_i = [0] * (INF+1)
for i,x in enumerate(P):
    x_to_i[x] = i

"""
・小さい方から埋めていく。
・埋めた位置に対して、「連結成分の左端」「連結成分の右端」を持つ
・区間の両端については、正しい値が入っている状態を保つ
"""

left = list(range(N+4))
right = list(range(N+4))
filled = [False] * (N+4)

answer = 0
for x,i in enumerate(x_to_i[1:N+1],1):
    filled[i] = True
    L = left[i-1] if filled[i-1] else i
    R = right[i+1] if filled[i+1] else i
    right[L] = R; left[R] = L
    # 自身より大きい場所。左右に2つずつ。
    c = i
    b = L-1; d = R+1
    a = left[L-3] if filled[L-2] else L-2
    e = right[R+3] if filled[R+2] else R+2
    coef = 0
    if b>=2: # 最大値をb,cとして選ぶ
        coef += (b-a)*(d-c)
    if d<=N+1:
        coef += (e-d)*(c-b)
    answer += x*coef

print(answer)

Submission status: Wrong Answer

Solution code:
n=int(input())
p=list(map(int,input().split()))
l=0
r=2
a=0
while l<n-1:
  p1=p[l:r]
  p1.sort()
  a+=p1[1]
  r+=1
  if r==n+1:
    l+=1
    r=l+2
print(a)

Submission status: Wrong Answer

Solution code:
import time
N = int(input())
Pn = list(map(int, input().split()))
ret = 0
for i in range(N - 1):
    max1No = i
    max2No = i + 1
    max1 = Pn[max1No]
    max2 = Pn[max2No]
    for j in range(i + 1, N):
        if(Pn[j] > max1):
            max2 = max1
            max1 = Pn[j]
        ret += max2
print(ret)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = list(map(int,input().split()))
ans = list()
for x in range(N-1):
  l = list()
  l.append(P[x])
  l.append(P[x+1])
  if len(l) == 2:
    ans.append(sorted(l)[-2])
  for y in range(N-1-x):
    if P[x+1+y] > ans[-1] and P[x+1+y] < max(l):
      ans.append(P[x+1+y])
    else:
      ans.append(ans[-1])
print(sum(ans))

Submission status: Wrong Answer

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

index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index

left_next_Index = list(range(-1, N - 1)) + [-1]
right_next_Index = list(range(1, N + 1)) + [N]
# print (left_next_Index)
# print (right_next_Index)
ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    # print (i, index)
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    # print ('l1 =', l1, ' l2 =', l2, ' r1 =', r1, ' r2 =', r2)
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))

    left_next_Index[r1] = l1
    right_next_Index[l1] = r1

print (ans)

Submission status: Wrong Answer

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

sum = 0
P.sort()
for L in range(len(P)-1):
    for R in range(L+1,len(P)):
        sortlist = P[L:R+1]
        sum += sortlist[len(sortlist)-2]

print(sum)

Submission status: Wrong Answer

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

sum = 0
P.sort()
for L in range(len(P)-1):
    for R in range(L+1,len(P)):
        sum += P[R-1]

print(sum)

Submission status: Wrong Answer

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

sum = 0
for L in range(len(P)-1):
    for R in range(L+1,len(P)):
        sortlist = sorted(P[L:R+1])
        if len(sortlist) < 3:
            sum += sortlist[0]
        else:
            sum += sortlist[1]

print(sum)

Submission status: Wrong Answer

Solution code:
#n = int(input())
#ListP =[int(i) for i in input().split()]
n = 10000
ListP = [i for i in range(n)]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
ListPos = [0, 0] + [ListPos2[n]] + [n+1, n+1]
#ListTPos = [0] * (n+2) + [n+1, n+1]
ListTPos = [0] * (n + 1) + [n+1]
ListTPos[ListPos2[n]] = ListPos2[n]
pos = 0
for i in reversed(range(1,n)):
	posi = ListPos2[i]
	ListTPos[posi] =  posi
	for j in ListTPos[posi+1:]:
		if (j > 0):
			pos = ListPos.index(j)
			ListPos.insert(pos, posi)
			#pos = ListTPos[j]
			break
	l1 = ListPos[pos-1]
	l2 = ListPos[pos-2]
	h1 = ListPos[pos+1]
	h2 = ListPos[pos+2]
	points += i * ((posi-l1)*(h2-h1) + (h1-posi)*(l1-l2))
	#low1 = ListPos[pos] - ListPos[pos-1]
	#low2 = ListPos[pos-1] - ListPos[pos-2]
	#high1 = ListPos[pos+1] - ListPos[pos]
	#high2 = ListPos[pos+2] - ListPos[pos+1]
	#points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Submission status: Wrong Answer

Solution code:
n = int(input())
P = list([int(x) for x in input().split()])
P_i = sorted(range(len(P)), key=lambda k: P[k], reverse=True)
S = {0, n+1}
ans = 0

for i in P_i:
    if i!=0:
        S1 = {j for j in range(0,i+1)}
        l1 = sorted(S.intersection(S1))[-1]
        if l1 == 0:
            l2 = 0
        else:
            l2 = sorted(S.intersection(S1))[-2]
        h1 = sorted(S.difference(S1))[0]
        if h1 == n+1:
            h2 = n+1
        else:
            h2 = sorted(S.difference(S1))[1]
        
        ans += P[i] * ((l1-l2)*(h1-(i+1)) + (i+1-l1)*(h2-h1))
        S.add(i+1)
    else:
        S.add(i+1)
print(ans)

Submission status: Wrong Answer

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

class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + 1
    s.T[k - 1] = max(s.T[k - 1], v)
    k += k & -k
    while k <= s.N:
      s.T[k - 1] = max(s.T[k - 1], v)
      k += k & -k
  def getV(s, x):
    if x < 0:
      return 0
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans = max(ans, s.T[x - 1])
      x -= x & -x
    return ans

class segMin:
  inf = N + 1
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    if l > r:
      return s.inf
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

ans = 0
D = [0] * (N + 1)
for i in range(N):
  D[P[i]] = i + 1

TMa = BIT(N + 1)
TMi = segMin(N + 1)

for i in range(N, 0, -1):
  #print(ans)
  t = D[i]
  ma = TMa.getV(t)
  ma2 = TMa.getV(ma)

  mi = TMi.getV(t, N + 1)
  mi2 = TMi.getV(mi + 1, N + 1)
  TMa.update(t, t)
  TMi.update(t, t)
  ans += (mi - t) * (ma - ma2) * i
  ans += (mi2 - mi) * (t - ma) * i

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
import random
import bisect
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class BIT:
    '''
    BinaryIndexedTreeのクラス。0-indexed に統一してあるので0からn-1までの配列と思って使える。

    Parameters
    ----------
        n (Union(int, list)): int なら使う BIT のサイズ。list ならそのlistで BIT を初期化する
    '''
    def __init__(self, x, d=0):
        if isinstance(x, int):
            self.size = x
            self.tree = [d for _ in range(self.size + 1)]
        elif isinstance(x, list):
            self.size = len(x)
            self.tree = [d for _ in range(self.size + 1)]
            self.build(x)
        else:
            raise TypeError

    def build(self, arr):
        """
        初期化されたあとのBITをリストの値に設定する

        Parameters
        ----------
            arr (list): 元のlsit

        Raises
        ------
            TypeError: 入力はlistでないといけないことに注意してください。
        """
        if not isinstance(arr, list):
            raise TypeError
        for num, x in enumerate(arr):
            self.add(num, x)

    def sum(self, i):
        '''[0,i) の和'''
        if i < 0:
            return 0
        s = self.tree[0]
        while i > 0:
            s += self.tree[i]
            i -= (i & -i)
        return s

    def add(self, i, a):
        i += 1
        '''i番目の要素にaを足す'''
        if(i == 0):
            return
        while (i <= self.size):
            self.tree[i] += a
            i += (i & -i)

    def lower_bound(self, w):
        '''[0,i]の和 >= w をみたす最小の index
        Examples
        ----------
        >>> bit = BIT([1,0,0,1,0,1,0])
        >>> bit.lower_bound(1)
        0
        >>> bit.lower_bound(2)
        3
        >>> bit.lower_bound(3)
        5
        '''
        if w <= 0:
            return -1
        x = 0
        k = 1 << (self.size.bit_length() - 1)
        while k:
            if x + k <= self.size and self.tree[x + k] < w:
                w -= self.tree[x + k]
                x += k
            k >>= 1
        return x

    def getKthNum(self, w):
        '''k番目(k = 0, 1, ...)に小さい数を返す'''
        w += 1
        return self.lower_bound(w)

    def upper_bound(self, w):
        w += 0.00000000001
        return self.lower_bound(w)

    def query(self, l, r):
        '''[l, r)の和を求める
        >>> bit = BIT([1,2,3,4,5])
        >>> bit.query(1,4)
        9
        >>> bit.query(0,2)
        3
        '''
        return self.sum(r) - self.sum(l)

    # 出力関係（デバッグのみに用いる）
    def __getitem__(self, item):
        if not isinstance(item, int):
            _tmp = item.indices(self.size + 1)
            return [self.sum(i + 1) - self.sum(i) for i in range(_tmp[0], _tmp[1], _tmp[2])]
        else:
            return self.sum(item + 1) - self.sum(item)
    def __str__(self):
        return str(self[0:self.size])
# END CUT HERE

class sqrtDecomposition():
    def __init__(self, N):
        self.BASE = int(sqrt(N * 10))
        self.size = 0
        self.a = [[] for i in range(ceil(N / self.BASE))]
        self.b = BIT(ceil(N / self.BASE))

    def insert(self, i):
        self.size += 1
        idx = bisect.bisect_left(self.a[i // self.BASE], i)
        self.a[i // self.BASE].insert(idx, i)
        self.b.add(i // self.BASE, 1)
        return (i // self.BASE, idx)

    def _next(self, key, idx1, idx2):
        if key >= self.size:
            return (None, None)
        if len(self.a[idx1]) - 1 == idx2:
            idx = self.b.lower_bound(key + 1)
            return (idx, 0)
        else:
            return (idx1, idx2 + 1)

    def _prev(self, key, idx1, idx2):
        if key <= 0:
            return (None, None)
        if idx2 == 0:
            idx = self.b.lower_bound(key)
            return (idx, len(self.a[idx]) - 1)
        else:
            return (idx1, idx2 - 1)

    def get(self, left, right):
        left += 1
        right += 1
        idx1, idx2 = None, None
        for key in range(left, right):
            # debug(key, self.size)
            if key <= 0 or key > self.size:
                yield (None, None)
                continue
            if not idx1:
                idx1 = self.b.lower_bound(key)
                idx2 = key - self.b.sum(idx1) - 1
            else:
                idx1, idx2 = self._next(key - 1, idx1, idx2)
            yield (idx1, idx2)

def main():
    # N = 10**5
    # P = [i for i in range(N)]
    # random.shuffle(P)
    N = ii()
    P = lmi()
    t = sqrtDecomposition(N)
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    # debug(L)
    ans = 0
    for num, i in enumerate(L):
        c = t.insert(i)
        idx = t.b.sum(c[0]) + c[1]
        l = [-1] * 4
        l[1] = t._prev(idx, *c)
        l[0] = t._prev(idx - 1, *l[1])
        l[2] = t._next(idx + 1, *c)
        l[3] = t._next(idx + 2, *l[2])
        # debug(idx, l[0], l[1], l[2], l[3])
        for j in range(4):
            if l[j][0] is not None:
                l[j] = t.a[l[j][0]][l[j][1]]
            else:
                if j >= 2:
                    l[j] = N
                else:
                    l[j] = -1

        # debug(l[0], l[1], l[2], l[3])
        ans += (abs(i - l[1]) * abs(l[3] - l[2]) + abs(l[1] - l[0]) * abs(l[2] - i)) * (N - num)
    # print(ans)
    return


if __name__ == '__main__':
    if not __debug__:
        import doctest
        doctest.testmod()
        import cProfile
        cProfile.run('for i in range(100): main()', sort=1)
    else:
        main()