Problem p02919 (python)

Fixed submission:
#incited from https://juppy.hatenablog.com/entry/2019/02/26/python_AVL%E6%9C%A8_%E9%85%8D%E5%88%97ver_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder_
#AVL-Tree code by edamat

class Avltree:
    """
    AVL木
 
    Methods
    -------
        search(x: int) -> Union(int)
            ◯.data == x のものが存在するある場合それを出力、ない場合 None を返す
        insert(x: int) -> None
            ◯.data == x がない場合 ◯.data == x なる頂点を作る。ある場合はなにもしない（上書きしない）
        y.to_s() -> int
            頂点yのdataを返す
        y.left_s() -> Union(int, key=None)
            頂点yのleftを返す(ない場合は key)
        search_lower(x: int, key_lower) -> int
            ○.data が x より小さいものの中で最も大きいものを出力、ない場合 key_lower を返す
        search_higher(x:int , key_higher) -> int
            ○.data が x より大きいものの中で最も小さいものを出力、ない場合 key_higher を返す
    """
 
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"
 
    def search(self, key):
        node = self
        while node is not None:
            if node.key == key:
                return node  # node.key == keyの場合
            if node.key > key:
                node = node.left
            elif node.key < key:
                node = node.right
        return None
 
    def search_lower(self, key, key_lower):
        node = self
        if node.key is None:
            return key_lower
        ans = key_lower
        while node is not None:
            if node.key < key:
                if ans < node.key:
                    ans = node.key
                node = node.right
            elif node.key >= key:
                node = node.left
        return ans
 
    def search_higher(self, key, key_higher):
        node = self
        if node.key is None:
            return key_higher
        ans = key_higher
        while node is not None:
            if node.key > key:
                if ans > node.key:
                    ans = node.key
                node = node.left
            elif node.key <= key:
                node = node.right
        return ans
 
 
    def end_lower(self, end_lower_key):
        node = self
        while node.left is not None:
            node = node.left
        return node.key
 
    def end_higher(self, end_higher_key):
        node = self
        while node.right is not None:
            node = node.right
        return node.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 is None:  # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left is None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self, key)
        elif key > self.key:
            if self.right is 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
        node = self
        s = []
        while True:
            if node.key > key:
                s.append((node, -1))
                if node.left is None:
                    node.left = Avltree(key)
                    node = node.left
                    break
                else:
                    node = node.left
            elif node.key < key:
                s.append((node, 1))
                if node.right is None:
                    node.right = Avltree(key)
                    node = node.right
                    break
                else:
                    node = node.right
        while len(s) != 0:
            node, direct = s.pop()
            if len(s) != 0:
                par = s[-1][0]
            else:
                par = p
            if direct == -1:
                if node.balance == "Right":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Left"
                elif node.balance == "Left":
                    if node.left.balance == "Right":
                        node.replace(par, node.DoubleRightRotation())
                    elif node.left.balance == "Left":
                        node.replace(par, node.SingleRightRotation())
                    break
            elif direct == 1:
                if node.balance == "Left":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Right"
                elif node.balance == "Right":
                    if node.right.balance == "Left":
                        node.replace(par, node.DoubleLeftRotation())
                    elif node.right.balance == "Right":
                        node.replace(par, node.SingleLeftRotation())
                    break
 
    def to_s(self):
        return self.key
    def left_s(self):
        if self.left is None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right is None:
            return None
        return (self.right).key

n=int(input())
arr=list(map(int,input().split()))
arr2=[[arr[i],i+1] for i in range(n)]
arr2=sorted(arr2,reverse=True,key=lambda x:x[0])
avl=Avltree()
ans=0
avl.insert(0)
avl.insert(n+1)
for val,pos in arr2:
  fl=avl.search_lower(pos,0)
  if fl==0:
    sl=0
  else:
    sl=avl.search_lower(fl,0)
  fr=avl.search_higher(pos,n+1)
  if fr==n+1:
    sr=n+1
  else:
    sr=avl.search_higher(fr,n+1)
  cnt=(fl-sl)*(fr-pos)+(pos-fl)*(sr-fr)
  ans+=cnt*val
  avl.insert(pos)
print(ans)

Buggy submission (verdict: Runtime Error):
#incited from https://juppy.hatenablog.com/entry/2019/02/26/python_AVL%E6%9C%A8_%E9%85%8D%E5%88%97ver_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder_
#AVL Tree code by juppy

#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

n=int(input())
arr=list(map(int,input().split()))
arr2=[[arr[i],i+1] for i in range(n)]
arr2=sorted(arr2,reverse=True,key=lambda x:x[0])
avl_key=[0]
avl_left=[None]*(n+2)
avl_right=[None]*(n+2)
balance=[0]*(n+2)
ans=0
insert(0,n+1)
for i in range(n):
  val,pos=arr2[i]
  fl=search_lower(0,pos,None)
  if fl==0:
    sl=0
  else:
    sl=search_lower(0,fl,None)
  fr=search_higher(0,pos,None)
  if fr==n+1:
    sr=n+1
  else:
    sr=search_higher(0,fr,None)
  cnt=(fl-sl)*(fr-pos)+(pos-fl)*(sr-fr)
  ans+=cnt*val
  print(sl,fl,pos,fr,sr,cnt,val,tmp)
  insert(0,pos)
print(ans)

Buggy submission (verdict: Runtime Error):
#incited from https://juppy.hatenablog.com/entry/2019/02/26/python_AVL%E6%9C%A8_%E9%85%8D%E5%88%97ver_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder_
#AVL-Tree code by juppy

#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

n=int(input())
arr=list(map(int,input().split()))
arr2=[[arr[i],i+1] for i in range(n)]
arr2=sorted(arr2,reverse=True,key=lambda x:x[0])
avl_key=[0]
avl_left=[None]*n
avl_right=[None]*n
balance=[0]*n
ans=0
for i in range(n):
  val,pos=arr2[i]
  fl=search_lower(0,pos,0)
  if fl!=0:
    sl=search_lower(0,fl,-1)
    if sl==-1:
      sl=0
  else:
    sl=0
  fr=search_higher(0,pos,n+1)
  if fr!=n+1:
    sr=search_higher(0,fr,-1)
    if sr==-1:
      sr=n+1
  else:
    sr=n+1
  cnt=(fl-sl)*(fr-pos)+(pos-fl)*(sr-fr)
  ans+=cnt*val
  insert(0,pos)
print(ans)