Buggy python submission (verdict: Time Limit Exceeded):
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.basesize=len(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]=base[i-self.num]
            for i in range(self.num+self.basesize, self.treesize):self.tree[i]=ini
            #segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
            for i in range(self.num-1,-1,-1):
                self.tree[i]=monoid(self.tree[2*i+1],self.tree[2*i+2])
        
        #条件を満たす(サンプルの条件はs以下になること)最大のインデックスを返す関数
        def max_index(self,index_func):
            #探していく
            i=0
            while i<self.num:
                k=2*i+1
                if index_func(self.tree[k+1]):
                    i=k+1
                    continue
                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 index_func(self.tree[k]):
                    i=k
                    continue
                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%2==0:
                    r-=1
                    ret=self.monoid(ret,self.tree[r])
                if l%2==0:
                    ret=self.monoid(ret,self.tree[l])
                    l+=1
                l//=2
                r//=2
            return ret
    
        #base[i]をsに更新したときにセグ木全体を更新する関数
        def update(self,index,new_value):
            i=index+self.num
            self.tree[i]=new_value
            while i!=0:
                i=(i-1)//2
                temp=self.monoid(self.tree[2*i+1],self.tree[2*i+2])
                if self.tree[i]!=temp:
                    self.tree[i]=temp
                    continue
                break

    #s=segtree([1,2,3],max,0)
    #print(s.tree)
    
    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()



Fixed submission:
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
    #print(d)
    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(cnt2,k2,i-2,k1,cnt1)
    print(ans)
main()

Buggy python submission (verdict: Time Limit Exceeded):
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%2==0:
                    r-=1
                    ret=self.monoid(ret,self.tree[r])
                if l%2==0:
                    ret=self.monoid(ret,self.tree[l])
                    l+=1
                l//=2
                r//=2
            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([1,2,3],max,0)
    #print(s.tree)
    
    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()

Fixed submission:
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
    #print(d)
    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(cnt2,k2,i-2,k1,cnt1)
    print(ans)
main()

Buggy python submission (verdict: Time Limit Exceeded):
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%2==0:
                    r-=1
                    ret=self.monoid(ret,self.tree[r])
                if l%2==0:
                    ret=self.monoid(ret,self.tree[l])
                    l+=1
                l//=2
                r//=2
            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([1,2,3],max,0)
    #print(s.tree)
    
    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()

Fixed submission:
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
    #print(d)
    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(cnt2,k2,i-2,k1,cnt1)
    print(ans)
main()

Buggy python submission (verdict: Time Limit Exceeded):
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%2==0:
                    r-=1
                    ret=self.monoid(ret,self.tree[r])
                if l%2==0:
                    ret=self.monoid(ret,self.tree[l])
                    l+=1
                l//=2
                r//=2
            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([1,2,3],max,0)
    #print(s.tree)
    
    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()



Fixed submission:
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
    #print(d)
    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(cnt2,k2,i-2,k1,cnt1)
    print(ans)
main()

Buggy python submission (verdict: Time Limit Exceeded):
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:
                k1=aa
                break
            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:
                cnt1=min(aa,n+2)-k1
                break
            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()

Fixed submission:
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
    #print(d)
    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(cnt2,k2,i-2,k1,cnt1)
    print(ans)
main()

Buggy python submission (verdict: Runtime Error):
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)])
        
        #条件を満たす(サンプルの条件は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):
            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
    
        #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)

    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:
                k2=aa
                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()

Fixed submission:
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
    #print(d)
    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(cnt2,k2,i-2,k1,cnt1)
    print(ans)
main()

Buggy python submission (verdict: Time Limit Exceeded):
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)])
        
        #条件を満たす(サンプルの条件は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):
            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
    
        #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()

Fixed submission:
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
    #print(d)
    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(cnt2,k2,i-2,k1,cnt1)
    print(ans)
main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    #from itertools import permutations as p
    n=int(input())
    a=list(map(int,input().split()))
    #n=3
    #a=[n-i for i in range(n)]
    #a=[1,3,2,4,6,5]
    n=len(a)

    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)])
        
        #条件を満たす(サンプルの条件は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):
            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
    
        #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)

    #a,bには下限と上限、valueにはOKな範囲のときはTrue、そうでないときにFalseを返す関数を入れる
    #limは下限を知りたいときはlower、上限を知りたいときはupperを入れる
    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 value_u(a,ini,border):return a
                else:return b
            elif value_u(med,ini,border):b=med
            else:a=med+1

    def value_u(i,ini,border):
        if s.search(ini,i+1)>border:
            return True
        else:
            return False

    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 value_d(b,ini,border):return b
                else:return a
            elif value_d(med,ini,border):a=med
            else:b=med-1
    def value_d(i,ini,border):
        if s.search(i,ini+1)>border:
            return True
        else:
            return False

    def calc(q):
        d=[0]*n
        for i in range(n):
            d[q[i]-1]=i
        ans=0
        for i in range(n-1):
            k1=n
            cnt1=n
            for j in range(d[i]+1,n):
                if q[j]>i+1:
                    k1=j
                    break
            for j in range(k1+1,n):
                if q[j]>i+1:
                    cnt1=j
                    break
            k2=-1
            cnt2=-1
            for j in range(d[i]-1,-1,-1):
                if q[j]>i+1:
                    k2=j
                    break
            for j in range(k2-1,-1,-1):
                if q[j]>i+1:
                    cnt2=j
                    break
            print(cnt2,k2,d[i],k1,cnt1)
            ans+=((k2-cnt2)*(k1-d[i])+(cnt1-k1)*(d[i]-k2))*(i+1)
        return ans

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

    #for i in p(a):
    #    if calc(i)!=calc2(i):
    #        print(i,calc(i),calc2(i))
main()

Fixed submission:
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
    #print(d)
    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(cnt2,k2,i-2,k1,cnt1)
    print(ans)
main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    #from itertools import permutations as p
    n=int(input())
    a=list(map(int,input().split()))
    #n=3
    #a=[n-i for i in range(n)]
    #a=[1,3,2,4,6,5]
    n=len(a)

    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)])
        
        #条件を満たす(サンプルの条件は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):
            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
    
        #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)

    #a,bには下限と上限、valueにはOKな範囲のときはTrue、そうでないときにFalseを返す関数を入れる
    #limは下限を知りたいときはlower、上限を知りたいときはupperを入れる
    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 value_u(a,ini,border):return a
                else:return b
            elif value_u(med,ini,border):b=med
            else:a=med+1

    def value_u(i,ini,border):
        if s.search(ini,i+1)>border:
            return True
        else:
            return False

    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 value_d(b,ini,border):return b
                else:return a
            elif value_d(med,ini,border):a=med
            else:b=med-1
    def value_d(i,ini,border):
        if s.search(i,ini+1)>border:
            return True
        else:
            return False

    def calc(q):
        d=[0]*n
        for i in range(n):
            d[q[i]-1]=i
        ans=0
        for i in range(n-1):
            k1=n
            cnt1=n
            for j in range(d[i]+1,n):
                if q[j]>i+1:
                    k1=j
                    break
            for j in range(k1+1,n):
                if q[j]>i+1:
                    cnt1=j
                    break
            k2=-1
            cnt2=-1
            for j in range(d[i]-1,-1,-1):
                if q[j]>i+1:
                    k2=j
                    break
            for j in range(k2-1,-1,-1):
                if q[j]>i+1:
                    cnt2=j
                    break
            print(cnt2,k2,d[i],k1,cnt1)
            ans+=((k2-cnt2)*(k1-d[i])+(cnt1-k1)*(d[i]-k2))*(i+1)
        return ans

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

    #for i in p(a):
    #    if calc(i)!=calc2(i):
    #        print(i,calc(i),calc2(i))
main()

Fixed submission:
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
    #print(d)
    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(cnt2,k2,i-2,k1,cnt1)
    print(ans)
main()