Buggy python submission (verdict: Runtime Error):
class B():
    def __init__(self,N):
        self.N = N
        self.node = [0]*(self.N+1)
        self.cnt = 0

    def add(self,x): # 要素 x を追加
        self.cnt += 1
        while x <= self.N:
            self.node[x] += 1
            x += x & -x

    def delete(self,x): # 要素 x を削除
        self.cnt -= 1
        while x <= self.N:
            self.node[x] -= 1
            x += x & -x

    def count(self,x): # x以下の要素数
        tmp = 0
        while x > 0:
            tmp += self.node[x]
            x -= x & -x
        return tmp

    def get_max(self):
        return self.get_ith(self.cnt)

    def get_ith(self,i): # i 番目に小さい要素を取得
        NG = -1
        OK = self.N+1
        while OK-NG > 1:
            mid = (OK+NG)//2
            #print(OK,NG,self.count(mid))
            if self.count(mid) >= i:
                OK = mid
            else:
                NG = mid
        return OK

    def search_low(self,x): # x より小さい最大の要素
        xcn = self.count(x)
        NG = -1
        OK = x
        while OK-NG > 1:
            mid = (OK+NG)//2
            #print(OK,NG,self.count(mid))
            if self.count(mid) >= xcn:
                OK = mid
            else:
                NG = mid
        return OK

    def search_high(self,x): # x より大きい最小の要素
        xcn = self.count(x)
        NG = x
        OK = self.N + 1
        while OK-NG > 1:
            mid = (OK+NG)//2
            #print(OK,NG,self.count(mid))
            if self.count(mid) > xcn:
                OK = mid
            else:
                NG = mid
        return OK

import sys

stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = nl()
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
ans = 0
b = B(n)
b.add(q[-1])
for i in range(n-1,0,-1):
  v = q[i]
  l1 = b.search_low(v)
  r1 = b.search_high(v)
  l2 = b.search_low(l1)
  r2 = b.search_high(r1)
  ans += i*((r1-v)*(l1-l2) + (v-l1)*(r2-r1))
  b.add(v)
print(ans)

Fixed submission:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = nl()
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
    
ans = 0
l = [0] + [i for i in range(n+1)]
r = [i+1 for i in range(n+1)] + [n+1]

for i in range(1,n+1):
    v = q[i]
    l1,r1 = l[v],r[v]
    l2,r2 = l[l1],r[r1]
    ans += i*((v-l1)*(r2-r1) + (r1-v)*(l1-l2))
    l[r1] = l1
    r[l1] = r1
  
print(ans)

Buggy python submission (verdict: Runtime Error):
class Avltree:
    """ Avl木を表現するクラス """
    def __init__(self):
        self.avl = [None,None,None,0]

    def node(self,key):
        return [None,key,None,0]

    # search(x) xが存在するならTrueをしないならFalseを返す
    # 使用法 Instance.search(x)
    def search(self,key,avl=None):
        if avl == None:
            avl = self.avl
        if key == avl[1]:
            return True
        elif key < avl[1]:
            if avl[0] == None:
                return False
            else:
                return self.search(key,avl[0])
        elif avl[1] < key:
            if avl[2] == None:
                return False
            else:
                return self.search(key,avl[2])
    
    # key未満で最大の要素を検索する。なければNoneを返す。
    # 使用法 Instance.search_lower(x)
    def search_lower(self,key,key_lower=None,avl=0):
        if avl == 0:
            avl = self.avl
        if avl == None:
            return key_lower
        elif key < avl[1]:
            if avl[0] == None:
                return key_lower
            else:
                return self.search_lower(key,key_lower,avl[0])
        elif avl[1] < key:
            key_lower = avl[1]
            if avl[2] == None:
                return key_lower
            else:
                return self.search_lower(key,key_lower,avl[2])
        #avl[1] == keyの場合
        if avl[0] == None:
            return key_lower
        else:
            if key_lower == None:
                return self.end_higher(avl[0][1],avl[0])
            else:
                return max(key_lower,self.end_higher(avl[0][1],avl[0]))
    
    # keyより大きい最小の要素を検索する。なければNoneを返す。
    # 使用法 Instance.search_higher(x)
    def search_higher(self,key,key_higher=None,avl=0):
        if avl == 0:
            avl = self.avl
        if avl == None:
            return key_higher
        if  key < avl[1]:
            key_higher = avl[1]
            if avl[0] == None:
                return key_higher
            else:
                return self.search_higher(key,key_higher,avl[0])
        if avl[1] < key:
            if avl[2] == None:
                return key_higher
            else:
                return self.search_higher(key,key_higher,avl[2])
        #self.key == keyの場合
        if avl[2] == None:
            return key_higher
        else:
            if key_higher == None:
                return self.end_lower(avl[2][1],avl[2])
            else:
                return min(key_higher,self.end_lower(avl[2][1],avl[2]))
    
    def end_lower(self,end_lower_key,avl=None):
        if avl == None:
            avl = self.avl
        if avl[0] == None:
            return end_lower_key
        else:
            end_lower_key = avl[0][1]
            return self.end_lower(end_lower_key,avl[0])
    def end_higher(self,end_higher_key,avl=None):
        if avl == None:
            avl = self.avl
        if avl[2] == None:
            return end_higher_key
        else:
            end_higher_key = avl[2][1]
            return self.end_higher(end_higher_key,avl[2])

    def DoubleRightRotation(self,avl):
        tl = avl[0]
        avl[0] = tl[2][2]
        tl[2][2] = avl # selfはそのノード
        tlr = tl[2]
        tl[2] = tlr[0]
        tlr[0] = tl
        if tlr[3] == 1:
            tlr[2][3] = 2
            tlr[0][3] = 0
        elif tlr[3] == 2:
            tlr[2][3] = 0
            tlr[0][3] = 1
        elif tlr[3] == 0:
            tlr[2][3] = 0
            tlr[0][3] = 0
        tlr[3] = 0
        return tlr

    def DoubleLeftRotation(self,avl):
        tr = avl[2]
        avl[2] = tr[0][0]
        tr[0][0] = avl
        trl = tr[0]
        tr[0] = trl[2]
        trl[2] = tr
        if trl[3] == 2:
            trl[0][3] = 1
            trl[2][3] = 0
        elif trl.balance == 1:
            trl[0][3] = 0
            trl[2][3] = 2
        elif trl.balance == 0:
            trl[0][3] = 0
            trl[2][3] = 0
        trl[3] = 0
        return trl

    def SingleLeftRotation(self,avl):
        tr = avl[2]
        tr[3] = 0
        avl[3] = 0
        avl[2] = tr[0]
        tr[0] = avl
        return tr

    def SingleRightRotation(self,avl):
        tl = avl[0]
        tl[3] = 0
        avl[3] = 0
        avl[0] = tl[2]
        tl[2] = avl
        return tl

    def replace(self,p,v,avl): # 親ノードpの下にある自分(avl)をvに置き換える。
        if p[0] is avl:
            p[0] = v
        else :
            p[2] = v
    
    # 木に要素を追加する。
    # 使用法 Instance.insert(x)
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.avl[1] == None: # rootを含むrotationはしないことにする。
            self.avl[1] = key
            return self.avl
        if key < self.avl[1]:
            if self.avl[0] == None:
                self.avl[0] = self.node(key)
            else:
                self.insertx(self.avl,key,self.avl[0])
        elif self.avl[1] < key:
            if self.avl[2] == None:
                self.avl[2] = self.node(key)
            else:
                self.insertx(self.avl,key,self.avl[2])
        else: # key == self.avl[1]:
            pass # do not overwrite
    def insertx(self,p,key,avl): # replaceを呼ぶために一つ上の親を持っているinsert
        if key < avl[1]:
            if avl[0] == None:
                avl[0] = self.node(key)
            else:
                if not self.insertx(avl,key,avl[0]): # 左の木が生長しなければ、
                    return False # 成長しない
            balance = avl[3]
            if balance == 2:
                avl[3] = 0
                return False
            elif balance == 0:
                avl[3] = 1
                return True # 成長した
            elif balance == 1:
                if avl[0][3] == 2:
                    self.replace(p,self.DoubleRightRotation(avl),avl)
               
                return False # rotationを行うと成長しない
        if avl[1] < key:
            if avl[2] == None:
                avl[2] = self.node(key)
            else:
                if not self.insertx(avl,key,avl[2]):
                    return False
            balance = avl[3]
            if balance == 1:
                avl[3] = 0
                return False
            elif balance == 0:
                avl[3] = 2
                return True
            elif balance == 2:
                if avl[2][3] == 1:
                    self.replace(p,self.DoubleLeftRotation(avl),avl)
                elif avl[2][3] == 2:
                    self.replace(p,self.SingleLeftRotation(avl),avl)
                return False
        return False # avl[1] == keyの時は何もしないので成長もしない

    def debug(self):
        print(self.avl)
def main():
    n = int(input())
    p = list(map(int,input().split()))
    q = [0]*(n+1)
    for i in range(n):
        q[p[i]] = i+1
    
    ans = 0
    avl = Avltree()
    avl.insert(q[n])
    for i in range(n-1,0,-1):
        cnt = 0
        v = q[i]
        lo = avl.search_lower(v)
        hi = avl.search_higher(v)
        #print(lo,hi)
        if lo:
            lo2 = avl.search_lower(lo,0)
            t = lo-lo2
            if hi:
                t *= hi - v
            else:
                t *= n+1 - v
            cnt += t
        if hi:
            hi2 = avl.search_higher(hi,n+1)
            t = hi2 - hi
            if lo:
                t *= v - lo
            else:
                t *= v
            cnt += t
        #print(cnt)
        ans += i*cnt
        avl.insert(v)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = nl()
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
    
ans = 0
l = [0] + [i for i in range(n+1)]
r = [i+1 for i in range(n+1)] + [n+1]

for i in range(1,n+1):
    v = q[i]
    l1,r1 = l[v],r[v]
    l2,r2 = l[l1],r[r1]
    ans += i*((v-l1)*(r2-r1) + (r1-v)*(l1-l2))
    l[r1] = l1
    r[l1] = r1
  
print(ans)

Buggy python submission (verdict: Runtime Error):
class Avltree:
    """ Avl木を表現するクラス """
    def __init__(self):
        self.avl = [None,None,None,0]

    def node(self,key):
        return [None,key,None,0]

    # search(x) xが存在するならTrueをしないならFalseを返す
    # 使用法 Instance.search(x)
    def search(self,key,avl=None):
        if avl == None:
            avl = self.avl
        if key == avl[1]:
            return True
        elif key < avl[1]:
            if avl[0] == None:
                return False
            else:
                return self.search(key,avl[0])
        elif avl[1] < key:
            if avl[2] == None:
                return False
            else:
                return self.search(key,avl[2])
    
    # key未満で最大の要素を検索する。なければNoneを返す。
    # 使用法 Instance.search_lower(x)
    def search_lower(self,key,key_lower=None,avl=0):
        if avl == 0:
            avl = self.avl
        if avl == None:
            return key_lower
        elif key < avl[1]:
            if avl[0] == None:
                return key_lower
            else:
                return self.search_lower(key,key_lower,avl[0])
        elif avl[1] < key:
            key_lower = avl[1]
            if avl[2] == None:
                return key_lower
            else:
                return self.search_lower(key,key_lower,avl[2])
        #avl[1] == keyの場合
        if avl[0] == None:
            return key_lower
        else:
            if key_lower == None:
                return self.end_higher(avl[0][1],avl[0])
            else:
                return max(key_lower,self.end_higher(avl[0][1],avl[0]))
    
    # keyより大きい最小の要素を検索する。なければNoneを返す。
    # 使用法 Instance.search_higher(x)
    def search_higher(self,key,key_higher=None,avl=0):
        if avl == 0:
            avl = self.avl
        if avl == None:
            return key_higher
        if  key < avl[1]:
            key_higher = avl[1]
            if avl[0] == None:
                return key_higher
            else:
                return self.search_higher(key,key_higher,avl[0])
        if avl[1] < key:
            if avl[2] == None:
                return key_higher
            else:
                return self.search_higher(key,key_higher,avl[2])
        #self.key == keyの場合
        if avl[2] == None:
            return key_higher
        else:
            if key_higher == None:
                return self.end_lower(avl[2][1],avl[2])
            else:
                return min(key_higher,self.end_lower(avl[2][1],avl[2]))
    
    def end_lower(self,end_lower_key,avl=None):
        if avl == None:
            avl = self.avl
        if avl[0] == None:
            return end_lower_key
        else:
            end_lower_key = avl[0][1]
            return self.end_lower(end_lower_key,avl[0])
    def end_higher(self,end_higher_key,avl=None):
        if avl == None:
            avl = self.avl
        if avl[2] == None:
            return end_higher_key
        else:
            end_higher_key = avl[2][1]
            return self.end_higher(end_higher_key,avl[2])

    def DoubleRightRotation(self,avl):
        tl = avl[0]
        avl[0] = tl[2][2]
        tl[2][2] = avl # selfはそのノード
        tlr = tl[2]
        tl[2] = tlr[0]
        tlr[0] = tl
        if tlr[3] == 1:
            tlr[2][3] = 2
            tlr[0][3] = 0
        elif tlr[3] == 2:
            tlr[2][3] = 0
            tlr[0][3] = 1
        elif tlr[3] == 0:
            tlr[2][3] = 0
            tlr[0][3] = 0
        tlr[3] = 0
        return tlr

    def DoubleLeftRotation(self,avl):
        tr = avl[2]
        avl[2] = tr[0][0]
        tr[0][0] = avl
        trl = tr[0]
        tr[0] = trl[2]
        trl[2] = tr
        if trl[3] == 2:
            trl[0][3] = 1
            trl[2][3] = 0
        elif trl.balance == 1:
            trl[0][3] = 0
            trl[2][3] = 2
        elif trl.balance == 0:
            trl[0][3] = 0
            trl[2][3] = 0
        trl[3] = 0
        return trl

    def SingleLeftRotation(self,avl):
        tr = avl[2]
        tr[3] = 0
        avl[3] = 0
        avl[2] = tr[0]
        tr[0] = avl
        return tr

    def SingleRightRotation(self,avl):
        tl = avl[0]
        tl[3] = 0
        avl[3] = 0
        avl[0] = tl[2]
        tl[2] = avl
        return tl

    def replace(self,p,v,avl): # 親ノードpの下にある自分(avl)をvに置き換える。
        if p[0] is avl:
            p[0] = v
        else :
            p[2] = v
    
    # 木に要素を追加する。
    # 使用法 Instance.insert(x)
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.avl[1] == None: # rootを含むrotationはしないことにする。
            self.avl[1] = key
            return self.avl
        if key < self.avl[1]:
            if self.avl[0] == None:
                self.avl[0] = self.node(key)
            else:
                self.insertx(self.avl,key,self.avl[0])
        elif self.avl[1] < key:
            if self.avl[2] == None:
                self.avl[2] = self.node(key)
            else:
                self.insertx(self.avl,key,self.avl[2])
        else: # key == self.avl[1]:
            pass # do not overwrite
    def insertx(self,p,key,avl): # replaceを呼ぶために一つ上の親を持っているinsert
        if key < avl[1]:
            if avl[0] == None:
                avl[0] = self.node(key)
            else:
                if not self.insertx(avl,key,avl[0]): # 左の木が生長しなければ、
                    return False # 成長しない
            balance = avl[3]
            if balance == 2:
                avl[3] = 0
                return False
            elif balance == 0:
                avl[3] = 1
                return True # 成長した
            elif balance == 1:
                if avl[0][3] == 2:
                    self.replace(p,self.DoubleRightRotation(avl),avl)
               
                return False # rotationを行うと成長しない
        if avl[1] < key:
            if avl[2] == None:
                avl[2] = self.node(key)
            else:
                if not self.insertx(avl,key,avl[2]):
                    return False
            balance = avl[3]
            if balance == 1:
                avl[3] = 0
                return False
            elif balance == 0:
                avl[3] = 2
                return True
            elif balance == 2:
                if avl[2][3] == 1:
                    self.replace(p,self.DoubleLeftRotation(avl),avl)
                elif avl[2][3] == 2:
                    self.replace(p,self.SingleLeftRotation(avl),avl)
                return False
        return False # avl[1] == keyの時は何もしないので成長もしない

    def debug(self):
        print(self.avl)
def main():
    n = int(input())
    p = list(map(int,input().split()))
    q = [0]*(n+1)
    for i in range(n):
        q[p[i]] = i+1
    
    ans = 0
    avl = Avltree()
    avl.insert(q[n])
    for i in range(n-1,0,-1):
        cnt = 0
        v = q[i]
        lo = avl.search_lower(v)
        hi = avl.search_higher(v)
        #print(lo,hi)
        if lo:
            lo2 = avl.search_lower(lo,0)
            t = lo-lo2
            if hi:
                t *= hi - v
            else:
                t *= n+1 - v
            cnt += t
        if hi:
            hi2 = avl.search_higher(hi,n+1)
            t = hi2 - hi
            if lo:
                t *= v - lo
            else:
                t *= v
            cnt += t
        #print(cnt)
        ans += i*cnt
        avl.insert(v)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = nl()
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
    
ans = 0
l = [0] + [i for i in range(n+1)]
r = [i+1 for i in range(n+1)] + [n+1]

for i in range(1,n+1):
    v = q[i]
    l1,r1 = l[v],r[v]
    l2,r2 = l[l1],r[r1]
    ans += i*((v-l1)*(r2-r1) + (r1-v)*(l1-l2))
    l[r1] = l1
    r[l1] = r1
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    #AVL
    
    ##search(0,x):O(logN)
    # xがある場合indexを、ない場合Noneを返す
    def search(root,key):
        if avl_key[root] > key:
            if avl_left[root] == None:
                return None
            else:
                return search(avl_left[root],key)
        if avl_key[root] < key:
            if avl_right[root] == None:
                return None
            else:
                return search(avl_right[root],key)
        return root
    
    
    ##end_lower/higher:search_lower/higherで使用
    def end_lower(root):
        if avl_left[root] == None:
            return avl_key[root]
        else:
            return end_lower(avl_left[root])
    
    def end_higher(root):
        if avl_right[root] == None:
            return avl_key[root]
        else:
            return end_higher(avl_right[root])
    
    
    ##search_lower(0,x,None):O(logN)
    # xより小さいものの中で最も大きいものを出力。ない場合はNoneを出力
    def search_lower(root,key,lower_key):
        if avl_key[root] > key:
            if avl_left[root] == None:
                return lower_key
            else:
                return search_lower(avl_left[root],key,lower_key)
        if avl_key[root] < key:
            lower_key = avl_key[root]
            if avl_right[root] == None:
                return lower_key
            else:
                return search_lower(avl_right[root],key,lower_key)
        
        # == 
        if avl_left[root] == None:
            return lower_key
        else:
            if lower_key == None:
                return end_higher(avl_left[root])
            else:
                return max(lower_key,end_higher(avl_left[root]))
    
    ##search_higher(0,x,None):O(logN)
    # xより大きいものの中で最も小さいものを出力。ない場合はNoneを出力
    def search_higher(root,key,higher_key):
        if avl_key[root] > key:
            higher_key = avl_key[root]
            if avl_left[root] == None:
                return higher_key
            else:
                return search_higher(avl_left[root],key,higher_key)
        if avl_key[root] < key:
            if avl_right[root] == None:
                return higher_key
            else:
                return search_higher(avl_right[root],key,higher_key)
        
        # == 
        if avl_right[root] == None:
            return higher_key
        else:
            if higher_key == None:
                return end_lower(avl_right[root])
            else:
                return min(higher_key,end_lower(avl_right[root]))
    
    
    
    ##Rotation,replace,insertx:insertで使用
    def DoubleRightRotation(x):
        tl = avl_left[x]
        avl_left[x] = avl_right[avl_right[tl]]
        avl_right[avl_right[tl]] = x
        tlr = avl_right[tl]
        avl_right[tl] = avl_left[tlr]
        avl_left[tlr] = tl
        if balance[tlr] == -1:
            balance[avl_right[tlr]] = 1
            balance[avl_left[tlr]] = 0
        elif balance[tlr] == 1:
            balance[avl_right[tlr]] = 0
            balance[avl_left[tlr]] = -1
        else:
            balance[avl_right[tlr]] = 0
            balance[avl_left[tlr]] = 0
        balance[tlr] = 0
        return tlr
    
    def DoubleLeftRotation(x):
        tr = avl_right[x]
        avl_right[x] = avl_left[avl_left[tr]]
        avl_left[avl_left[tr]] = x
        trl = avl_left[tr]
        avl_left[tr] = avl_right[trl]
        avl_right[trl] = tr
        if balance[trl] == 1:
            balance[avl_right[trl]] = 0
            balance[avl_left[trl]] = -1
        elif balance[trl] == -1:
            balance[avl_left[trl]] = 0
            balance[avl_right[trl]] = 1
        else:
            balance[avl_right[trl]] = 0
            balance[avl_left[trl]] = 0
        balance[trl] = 0
        return trl
    
    def SingleLeftRotation(x):
        tr = avl_right[x]
        balance[tr] = 0
        balance[x] = 0
        avl_right[x] = avl_left[tr]
        avl_left[tr] = x
        return tr
    
    def SingleRightRotation(x):
        tl = avl_left[x]
        balance[tl] = 0
        balance[x] = 0
        avl_left[x] = avl_right[tl]
        avl_right[tl] = x
        return tl
    
    def replace(x,p,v):
        if avl_left[p] == x:
            avl_left[p] = v
        else:
            avl_right[p] = v
    
    def insertx(root,p,key):
        if avl_key[root] > key:
            if avl_left[root] == None:
                avl_key.append(key)
                avl_left[root] = len(avl_key)-1
            else:
                if not insertx(avl_left[root],root,key):
                    return False
            if balance[root] == 1:
                balance[root] = 0
                return False
            elif balance[root] == 0:
                balance[root] = -1
                return True
            else:
                if balance[avl_left[root]] == 1:
                    replace(root,p,DoubleRightRotation(root))
                elif balance[avl_left[root]] == -1:
                    replace(root,p,SingleRightRotation(root))
                return False
        if avl_key[root] < key:
            if avl_right[root] == None:
                avl_key.append(key)
                avl_right[root] = len(avl_key)-1
            else:
                if not insertx(avl_right[root],root,key):
                    return False
            if balance[root] == -1:
                balance[root] = 0
                return False
            elif balance[root] == 0:
                balance[root] = 1
                return True
            else:
                if balance[avl_right[root]] == -1:
                    replace(root,p,DoubleLeftRotation(root))
                elif balance[avl_right[root]] == 1:
                    replace(root,p,SingleLeftRotation(root))
                return False
        return False
    
    
    ##insert(0,x):O(logN)
    #x追加
    def insert(root,key):
        if key < avl_key[root]:
            if avl_left[root] == None:
                avl_key.append(key)
                avl_left[root] = len(avl_key)-1
            else:
                insertx(avl_left[root],root,key)
        elif key > avl_key[root]:
            if avl_right[root] == None:
                avl_key.append(key)
                avl_right[root] = len(avl_key)-1
            else:
                insertx(avl_right[root],root,key)
        else:
            pass
    ########################################################
    ##初期化（要素は一つ入れておく）
    
    #avl_key:値,avl_left:左の子のindex,avl_right:右の子のindex
    #balance[i]: {"Even":0,"Left":-1,"Right":1}
    
    #avl_keyには初めに何か加えておく
    n = int(input())
    p = list(map(int,input().split()))
    q = [0]*(n+1)
    for i in range(n):
        q[p[i]] = i+1
    
    avl_key = [q[n]]
    avl_left = [None]*(n+1)
    avl_right = [None]*(n+1)
    balance = [0]*n
    
    ans = 0
    
    for i in range(n-1,0,-1):
        cnt = 0
        v = q[i]
        lo = search_lower(0,v,None)
        hi = search_higher(0,v,None)
        #print(lo,hi)
        if lo:
            lo2 = search_lower(0,lo,0)
            t = lo-lo2
            if hi:
                t *= hi - v
            else:
                t *= n+1 - v
            cnt += t
        if hi:
            hi2 = search_higher(0,hi,n+1)
            t = hi2 - hi
            if lo:
                t *= v - lo
            else:
                t *= v
            cnt += t
        #print(cnt)
        ans += i*cnt
        insert(0,v)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = nl()
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
    
ans = 0
l = [0] + [i for i in range(n+1)]
r = [i+1 for i in range(n+1)] + [n+1]

for i in range(1,n+1):
    v = q[i]
    l1,r1 = l[v],r[v]
    l2,r2 = l[l1],r[r1]
    ans += i*((v-l1)*(r2-r1) + (r1-v)*(l1-l2))
    l[r1] = l1
    r[l1] = r1
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    #AVL
    
    ##search(0,x):O(logN)
    # xがある場合indexを、ない場合Noneを返す
    def search(root,key):
        if avl_key[root] > key:
            if avl_left[root] == None:
                return None
            else:
                return search(avl_left[root],key)
        if avl_key[root] < key:
            if avl_right[root] == None:
                return None
            else:
                return search(avl_right[root],key)
        return root
    
    
    ##end_lower/higher:search_lower/higherで使用
    def end_lower(root):
        if avl_left[root] == None:
            return avl_key[root]
        else:
            return end_lower(avl_left[root])
    
    def end_higher(root):
        if avl_right[root] == None:
            return avl_key[root]
        else:
            return end_higher(avl_right[root])
    
    
    ##search_lower(0,x,None):O(logN)
    # xより小さいものの中で最も大きいものを出力。ない場合はNoneを出力
    def search_lower(root,key,lower_key):
        if avl_key[root] > key:
            if avl_left[root] == None:
                return lower_key
            else:
                return search_lower(avl_left[root],key,lower_key)
        if avl_key[root] < key:
            lower_key = avl_key[root]
            if avl_right[root] == None:
                return lower_key
            else:
                return search_lower(avl_right[root],key,lower_key)
        
        # == 
        if avl_left[root] == None:
            return lower_key
        else:
            if lower_key == None:
                return end_higher(avl_left[root])
            else:
                return max(lower_key,end_higher(avl_left[root]))
    
    ##search_higher(0,x,None):O(logN)
    # xより大きいものの中で最も小さいものを出力。ない場合はNoneを出力
    def search_higher(root,key,higher_key):
        if avl_key[root] > key:
            higher_key = avl_key[root]
            if avl_left[root] == None:
                return higher_key
            else:
                return search_higher(avl_left[root],key,higher_key)
        if avl_key[root] < key:
            if avl_right[root] == None:
                return higher_key
            else:
                return search_higher(avl_right[root],key,higher_key)
        
        # == 
        if avl_right[root] == None:
            return higher_key
        else:
            if higher_key == None:
                return end_lower(avl_right[root])
            else:
                return min(higher_key,end_lower(avl_right[root]))
    
    
    
    ##Rotation,replace,insertx:insertで使用
    def DoubleRightRotation(x):
        tl = avl_left[x]
        avl_left[x] = avl_right[avl_right[tl]]
        avl_right[avl_right[tl]] = x
        tlr = avl_right[tl]
        avl_right[tl] = avl_left[tlr]
        avl_left[tlr] = tl
        if balance[tlr] == -1:
            balance[avl_right[tlr]] = 1
            balance[avl_left[tlr]] = 0
        elif balance[tlr] == 1:
            balance[avl_right[tlr]] = 0
            balance[avl_left[tlr]] = -1
        else:
            balance[avl_right[tlr]] = 0
            balance[avl_left[tlr]] = 0
        balance[tlr] = 0
        return tlr
    
    def DoubleLeftRotation(x):
        tr = avl_right[x]
        avl_right[x] = avl_left[avl_left[tr]]
        avl_left[avl_left[tr]] = x
        trl = avl_left[tr]
        avl_left[tr] = avl_right[trl]
        avl_right[trl] = tr
        if balance[trl] == 1:
            balance[avl_right[trl]] = 0
            balance[avl_left[trl]] = -1
        elif balance[trl] == -1:
            balance[avl_left[trl]] = 0
            balance[avl_right[trl]] = 1
        else:
            balance[avl_right[trl]] = 0
            balance[avl_left[trl]] = 0
        balance[trl] = 0
        return trl
    
    def SingleLeftRotation(x):
        tr = avl_right[x]
        balance[tr] = 0
        balance[x] = 0
        avl_right[x] = avl_left[tr]
        avl_left[tr] = x
        return tr
    
    def SingleRightRotation(x):
        tl = avl_left[x]
        balance[tl] = 0
        balance[x] = 0
        avl_left[x] = avl_right[tl]
        avl_right[tl] = x
        return tl
    
    def replace(x,p,v):
        if avl_left[p] == x:
            avl_left[p] = v
        else:
            avl_right[p] = v
    
    def insertx(root,p,key):
        if avl_key[root] > key:
            if avl_left[root] == None:
                avl_key.append(key)
                avl_left[root] = len(avl_key)-1
            else:
                if not insertx(avl_left[root],root,key):
                    return False
            if balance[root] == 1:
                balance[root] = 0
                return False
            elif balance[root] == 0:
                balance[root] = -1
                return True
            else:
                if balance[avl_left[root]] == 1:
                    replace(root,p,DoubleRightRotation(root))
                elif balance[avl_left[root]] == -1:
                    replace(root,p,SingleRightRotation(root))
                return False
        if avl_key[root] < key:
            if avl_right[root] == None:
                avl_key.append(key)
                avl_right[root] = len(avl_key)-1
            else:
                if not insertx(avl_right[root],root,key):
                    return False
            if balance[root] == -1:
                balance[root] = 0
                return False
            elif balance[root] == 0:
                balance[root] = 1
                return True
            else:
                if balance[avl_right[root]] == -1:
                    replace(root,p,DoubleLeftRotation(root))
                elif balance[avl_right[root]] == 1:
                    replace(root,p,SingleLeftRotation(root))
                return False
        return False
    
    
    ##insert(0,x):O(logN)
    #x追加
    def insert(root,key):
        if key < avl_key[root]:
            if avl_left[root] == None:
                avl_key.append(key)
                avl_left[root] = len(avl_key)-1
            else:
                insertx(avl_left[root],root,key)
        elif key > avl_key[root]:
            if avl_right[root] == None:
                avl_key.append(key)
                avl_right[root] = len(avl_key)-1
            else:
                insertx(avl_right[root],root,key)
        else:
            pass
    ########################################################
    ##初期化（要素は一つ入れておく）
    
    #avl_key:値,avl_left:左の子のindex,avl_right:右の子のindex
    #balance[i]: {"Even":0,"Left":-1,"Right":1}
    
    #avl_keyには初めに何か加えておく
    n = int(input())
    p = list(map(int,input().split()))
    q = [0]*(n+1)
    for i in range(n):
        q[p[i]] = i+1
    
    avl_key = [q[n]]
    avl_left = [None]*(n+1)
    avl_right = [None]*(n+1)
    balance = [0]*n
    
    ans = 0
    
    for i in range(n-1,0,-1):
        cnt = 0
        v = q[i]
        lo = search_lower(0,v,None)
        hi = search_higher(0,v,None)
        #print(lo,hi)
        if lo:
            lo2 = search_lower(0,lo,0)
            t = lo-lo2
            if hi:
                t *= hi - v
            else:
                t *= n+1 - v
            cnt += t
        if hi:
            hi2 = search_higher(0,hi,n+1)
            t = hi2 - hi
            if lo:
                t *= v - lo
            else:
                t *= v
            cnt += t
        #print(cnt)
        ans += i*cnt
        insert(0,v)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = nl()
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
    
ans = 0
l = [0] + [i for i in range(n+1)]
r = [i+1 for i in range(n+1)] + [n+1]

for i in range(1,n+1):
    v = q[i]
    l1,r1 = l[v],r[v]
    l2,r2 = l[l1],r[r1]
    ans += i*((v-l1)*(r2-r1) + (r1-v)*(l1-l2))
    l[r1] = l1
    r[l1] = r1
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#AVL

##search(0,x):O(logN)
# xがある場合indexを、ない場合Noneを返す
def search(root,key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            return None
        else:
            return search(avl_left[root],key)
    if avl_key[root] < key:
        if avl_right[root] == None:
            return None
        else:
            return search(avl_right[root],key)
    return root


##end_lower/higher:search_lower/higherで使用
def end_lower(root):
    if avl_left[root] == None:
        return avl_key[root]
    else:
        return end_lower(avl_left[root])

def end_higher(root):
    if avl_right[root] == None:
        return avl_key[root]
    else:
        return end_higher(avl_right[root])


##search_lower(0,x,None):O(logN)
# xより小さいものの中で最も大きいものを出力。ない場合はNoneを出力
def search_lower(root,key,lower_key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            return lower_key
        else:
            return search_lower(avl_left[root],key,lower_key)
    if avl_key[root] < key:
        lower_key = avl_key[root]
        if avl_right[root] == None:
            return lower_key
        else:
            return search_lower(avl_right[root],key,lower_key)
    
    # == 
    if avl_left[root] == None:
        return lower_key
    else:
        if lower_key == None:
            return end_higher(avl_left[root])
        else:
            return max(lower_key,end_higher(avl_left[root]))

##search_higher(0,x,None):O(logN)
# xより大きいものの中で最も小さいものを出力。ない場合はNoneを出力
def search_higher(root,key,higher_key):
    if avl_key[root] > key:
        higher_key = avl_key[root]
        if avl_left[root] == None:
            return higher_key
        else:
            return search_higher(avl_left[root],key,higher_key)
    if avl_key[root] < key:
        if avl_right[root] == None:
            return higher_key
        else:
            return search_higher(avl_right[root],key,higher_key)
    
    # == 
    if avl_right[root] == None:
        return higher_key
    else:
        if higher_key == None:
            return end_lower(avl_right[root])
        else:
            return min(higher_key,end_lower(avl_right[root]))



##Rotation,replace,insertx:insertで使用
def DoubleRightRotation(x):
    tl = avl_left[x]
    avl_left[x] = avl_right[avl_right[tl]]
    avl_right[avl_right[tl]] = x
    tlr = avl_right[tl]
    avl_right[tl] = avl_left[tlr]
    avl_left[tlr] = tl
    if balance[tlr] == -1:
        balance[avl_right[tlr]] = 1
        balance[avl_left[tlr]] = 0
    elif balance[tlr] == 1:
        balance[avl_right[tlr]] = 0
        balance[avl_left[tlr]] = -1
    else:
        balance[avl_right[tlr]] = 0
        balance[avl_left[tlr]] = 0
    balance[tlr] = 0
    return tlr

def DoubleLeftRotation(x):
    tr = avl_right[x]
    avl_right[x] = avl_left[avl_left[tr]]
    avl_left[avl_left[tr]] = x
    trl = avl_left[tr]
    avl_left[tr] = avl_right[trl]
    avl_right[trl] = tr
    if balance[trl] == 1:
        balance[avl_right[trl]] = 0
        balance[avl_left[trl]] = -1
    elif balance[trl] == -1:
        balance[avl_left[trl]] = 0
        balance[avl_right[trl]] = 1
    else:
        balance[avl_right[trl]] = 0
        balance[avl_left[trl]] = 0
    balance[trl] = 0
    return trl

def SingleLeftRotation(x):
    tr = avl_right[x]
    balance[tr] = 0
    balance[x] = 0
    avl_right[x] = avl_left[tr]
    avl_left[tr] = x
    return tr

def SingleRightRotation(x):
    tl = avl_left[x]
    balance[tl] = 0
    balance[x] = 0
    avl_left[x] = avl_right[tl]
    avl_right[tl] = x
    return tl

def replace(x,p,v):
    if avl_left[p] == x:
        avl_left[p] = v
    else:
        avl_right[p] = v

def insertx(root,p,key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            avl_key.append(key)
            avl_left[root] = len(avl_key)-1
        else:
            if not insertx(avl_left[root],root,key):
                return False
        if balance[root] == 1:
            balance[root] = 0
            return False
        elif balance[root] == 0:
            balance[root] = -1
            return True
        else:
            if balance[avl_left[root]] == 1:
                replace(root,p,DoubleRightRotation(root))
            elif balance[avl_left[root]] == -1:
                replace(root,p,SingleRightRotation(root))
            return False
    if avl_key[root] < key:
        if avl_right[root] == None:
            avl_key.append(key)
            avl_right[root] = len(avl_key)-1
        else:
            if not insertx(avl_right[root],root,key):
                return False
        if balance[root] == -1:
            balance[root] = 0
            return False
        elif balance[root] == 0:
            balance[root] = 1
            return True
        else:
            if balance[avl_right[root]] == -1:
                replace(root,p,DoubleLeftRotation(root))
            elif balance[avl_right[root]] == 1:
                replace(root,p,SingleLeftRotation(root))
            return False
    return False


##insert(0,x):O(logN)
#x追加
def insert(root,key):
    if key < avl_key[root]:
        if avl_left[root] == None:
            avl_key.append(key)
            avl_left[root] = len(avl_key)-1
        else:
            insertx(avl_left[root],root,key)
    elif key > avl_key[root]:
        if avl_right[root] == None:
            avl_key.append(key)
            avl_right[root] = len(avl_key)-1
        else:
            insertx(avl_right[root],root,key)
    else:
        pass
########################################################
##初期化（要素は一つ入れておく）

#avl_key:値,avl_left:左の子のindex,avl_right:右の子のindex
#balance[i]: {"Even":0,"Left":-1,"Right":1}

#avl_keyには初めに何か加えておく
n = int(input())
p = list(map(int,input().split()))
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1

avl_key = [q[n]]
avl_left = [None]*(n+1)
avl_right = [None]*(n+1)
balance = [0]*n

ans = 0

for i in range(n-1,0,-1):
    cnt = 0
    v = q[i]
    lo = search_lower(0,v,None)
    hi = search_higher(0,v,None)
    #print(lo,hi)
    if lo:
        lo2 = search_lower(0,lo,0)
        t = lo-lo2
        if hi:
            t *= hi - v
        else:
            t *= n+1 - v
        cnt += t
    if hi:
        hi2 = search_higher(0,hi,n+1)
        t = hi2 - hi
        if lo:
            t *= v - lo
        else:
            t *= v
        cnt += t
    #print(cnt)
    ans += i*cnt
    insert(0,v)
print(ans)

Fixed submission:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = nl()
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
    
ans = 0
l = [0] + [i for i in range(n+1)]
r = [i+1 for i in range(n+1)] + [n+1]

for i in range(1,n+1):
    v = q[i]
    l1,r1 = l[v],r[v]
    l2,r2 = l[l1],r[r1]
    ans += i*((v-l1)*(r2-r1) + (r1-v)*(l1-l2))
    l[r1] = l1
    r[l1] = r1
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#root.search(x): ◯.data == x のものが存在するある場合それを出力、ない場合Noneを出力
#root.insert(x): ◯.data == xが存在する場合Falseを出力、ない場合◯.data == x なる頂点を作る
#y.to_s(): 頂点yのdataを出力
#y.left_s(): 頂点yのleftを出力(ない場合はNone)
#root.search_lower(x,None): ○.dataがxより小さいものの中で最も大きいものを出力、ない場合Noneを出力
#root.search_higher(x,None): xより大きいものの中で最も小さいものを出力、ない場合Noneを出力

################################################################################
class Avltree:
    def __init__(self,key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"
    def search(self,key):
        if self.key == None:
            return None
        if self.key > key:
            if self.left == None:
                return None
            else:
                return self.left.search(key)
        if self.key < key:
            if self.right == None:
                return None
            else:
                return self.right.search(key)
        return self # self.key == keyの場合

    def search_lower(self,key,key_lower):
        if self.key == None:
            return key_lower
        if self.key > key:
            if self.left == None:
                return key_lower
            else:
                return self.left.search_lower(key,key_lower)
        if self.key < key:
            key_lower = self.key
            if self.right == None:
                return key_lower
            else:
                return self.right.search_lower(key,key_lower)
        #self.key == keyの場合
        if self.left == None:
            return key_lower
        else:
            if key_lower == None:
                return self.left.end_higher(self.left.key)
            else:
                return max(key_lower,self.left.end_higher(self.left.key))

    def search_higher(self,key,key_higher):
        if self.key == None:
            return key_higher
        if self.key > key:
            key_higher = self.key
            if self.left == None:
                return key_higher
            else:
                return self.left.search_higher(key,key_higher)
        if self.key < key:
            if self.right == None:
                return key_higher
            else:
                return self.right.search_higher(key,key_higher)
        #self.key == keyの場合
        if self.right == None:
            return key_higher
        else:
            if key_higher == None:
                return self.right.end_lower(self.right.key)
            else:
                return min(key_higher,self.right.end_lower(self.right.key))


    def end_lower(self,end_lower_key):
        if self.left == None:
            return end_lower_key
        else:
            end_lower_key = self.left.key
            return self.left.end_lower(end_lower_key)
    def end_higher(self,end_higher_key):
        if self.right == None:
            return end_higher_key
        else:
            end_higher_key = self.right.key
            return self.right.end_higher(end_higher_key)


    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self,p,v): # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else :
            p.right = v
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.key == None: # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self,key)
        elif key > self.key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self,key)
        else: # key == self.key:
            pass # do not overwrite
    def insertx(self,p,key): # replaceを呼ぶために一つ上の親を持っているinsert
        if self.key > key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                if not self.left.insertx(self, key): # 左の木が生長しなければ、
                    return False # 成長しない
            if self.balance == "Right":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Left"
                return True # 成長した
            elif self.balance == "Left":
                if self.left.balance == "Right":
                    self.replace(p,self.DoubleRightRotation())
                elif self.left.balance == "Left":
                    self.replace(p,self.SingleRightRotation())
                return False # rotationを行うと成長しない
        if self.key < key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                if not self.right.insertx(self, key):
                    return False
            if self.balance == "Left":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Right"
                return True
            elif self.balance == "Right":
                if self.right.balance == "Left":
                    self.replace(p,self.DoubleLeftRotation())
                elif self.right.balance == "Right":
                    self.replace(p,self.SingleLeftRotation())
                return False
        return False # self.key == keyの時は何もしないので成長もしない

    def to_s(self):
        return self.key
    def left_s(self):
        if self.left == None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right == None:
            return None
        return (self.right).key

################################################################
n = int(input())
p = list(map(int,input().split()))
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
ans = 0
avl = Avltree()
avl.insert(q[n])
for i in range(n-1,0,-1):
    cnt = 0
    v = q[i]
    lo = avl.search_lower(v,None)
    hi = avl.search_higher(v,None)
    #print(lo,hi)
    if lo:
        lo2 = avl.search_lower(lo,0)
        t = lo-lo2
        if hi:
            t *= hi - v
        else:
            t *= n+1 - v
        cnt += t
    if hi:
        hi2 = avl.search_higher(hi,n+1)
        t = hi2 - hi
        if lo:
            t *= v - lo
        else:
            t *= v
        cnt += t
    #print(cnt)
    ans += i*cnt
    avl.insert(v)
print(ans)


Fixed submission:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = nl()
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
    
ans = 0
l = [0] + [i for i in range(n+1)]
r = [i+1 for i in range(n+1)] + [n+1]

for i in range(1,n+1):
    v = q[i]
    l1,r1 = l[v],r[v]
    l2,r2 = l[l1],r[r1]
    ans += i*((v-l1)*(r2-r1) + (r1-v)*(l1-l2))
    l[r1] = l1
    r[l1] = r1
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#root.search(x): ◯.data == x のものが存在するある場合それを出力、ない場合Noneを出力
#root.insert(x): ◯.data == xが存在する場合Falseを出力、ない場合◯.data == x なる頂点を作る
#y.to_s(): 頂点yのdataを出力
#y.left_s(): 頂点yのleftを出力(ない場合はNone)
#root.search_lower(x,None): ○.dataがxより小さいものの中で最も大きいものを出力、ない場合Noneを出力
#root.search_higher(x,None): xより大きいものの中で最も小さいものを出力、ない場合Noneを出力

################################################################################
class Avltree:
    def __init__(self,key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"
    def search(self,key):
        if self.key == None:
            return None
        if self.key > key:
            if self.left == None:
                return None
            else:
                return self.left.search(key)
        if self.key < key:
            if self.right == None:
                return None
            else:
                return self.right.search(key)
        return self # self.key == keyの場合

    def search_lower(self,key,key_lower):
        if self.key == None:
            return key_lower
        if self.key > key:
            if self.left == None:
                return key_lower
            else:
                return self.left.search_lower(key,key_lower)
        if self.key < key:
            key_lower = self.key
            if self.right == None:
                return key_lower
            else:
                return self.right.search_lower(key,key_lower)
        #self.key == keyの場合
        if self.left == None:
            return key_lower
        else:
            if key_lower == None:
                return self.left.end_higher(self.left.key)
            else:
                return max(key_lower,self.left.end_higher(self.left.key))

    def search_higher(self,key,key_higher):
        if self.key == None:
            return key_higher
        if self.key > key:
            key_higher = self.key
            if self.left == None:
                return key_higher
            else:
                return self.left.search_higher(key,key_higher)
        if self.key < key:
            if self.right == None:
                return key_higher
            else:
                return self.right.search_higher(key,key_higher)
        #self.key == keyの場合
        if self.right == None:
            return key_higher
        else:
            if key_higher == None:
                return self.right.end_lower(self.right.key)
            else:
                return min(key_higher,self.right.end_lower(self.right.key))


    def end_lower(self,end_lower_key):
        if self.left == None:
            return end_lower_key
        else:
            end_lower_key = self.left.key
            return self.left.end_lower(end_lower_key)
    def end_higher(self,end_higher_key):
        if self.right == None:
            return end_higher_key
        else:
            end_higher_key = self.right.key
            return self.right.end_higher(end_higher_key)


    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self,p,v): # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else :
            p.right = v
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.key == None: # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self,key)
        elif key > self.key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self,key)
        else: # key == self.key:
            pass # do not overwrite
    def insertx(self,p,key): # replaceを呼ぶために一つ上の親を持っているinsert
        if self.key > key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                if not self.left.insertx(self, key): # 左の木が生長しなければ、
                    return False # 成長しない
            if self.balance == "Right":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Left"
                return True # 成長した
            elif self.balance == "Left":
                if self.left.balance == "Right":
                    self.replace(p,self.DoubleRightRotation())
                elif self.left.balance == "Left":
                    self.replace(p,self.SingleRightRotation())
                return False # rotationを行うと成長しない
        if self.key < key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                if not self.right.insertx(self, key):
                    return False
            if self.balance == "Left":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Right"
                return True
            elif self.balance == "Right":
                if self.right.balance == "Left":
                    self.replace(p,self.DoubleLeftRotation())
                elif self.right.balance == "Right":
                    self.replace(p,self.SingleLeftRotation())
                return False
        return False # self.key == keyの時は何もしないので成長もしない

    def to_s(self):
        return self.key
    def left_s(self):
        if self.left == None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right == None:
            return None
        return (self.right).key

################################################################
n = int(input())
p = list(map(int,input().split()))
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
ans = 0
avl = Avltree()
avl.insert(q[n])
for i in range(n-1,0,-1):
    cnt = 0
    v = q[i]
    lo = avl.search_lower(v,None)
    hi = avl.search_higher(v,None)
    #print(lo,hi)
    if lo:
        lo2 = avl.search_lower(lo,0)
        t = lo-lo2
        if hi:
            t *= hi - v
        else:
            t *= n+1 - v
        cnt += t
    if hi:
        hi2 = avl.search_higher(hi,n+1)
        t = hi2 - hi
        if lo:
            t *= v - lo
        else:
            t *= v
        cnt += t
    #print(cnt)
    ans += i*cnt
    avl.insert(v)
print(ans)

Fixed submission:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = nl()
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
    
ans = 0
l = [0] + [i for i in range(n+1)]
r = [i+1 for i in range(n+1)] + [n+1]

for i in range(1,n+1):
    v = q[i]
    l1,r1 = l[v],r[v]
    l2,r2 = l[l1],r[r1]
    ans += i*((v-l1)*(r2-r1) + (r1-v)*(l1-l2))
    l[r1] = l1
    r[l1] = r1
  
print(ans)