Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
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

################################################################

#test



#検索 O(log N)
#root.search(x): ◯.data == x のものが存在するある場合それを出力、ない場合Noneを出力
#y.to_s(): 頂点yのdataを出力
#y.left_s(): 頂点yのleftを出力(ない場合はNone)

#1-20があるか、あるならその左右は何なのか


n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    b[a[i]-1]=i
avl=Avltree()
count=0
avl.insert(-1)
avl.insert(n)
# avl.debug()
for i in range(n):
    # print(avl.search_lower(b[i],None))
    # print(avl.search_higher(b[i],None))
    # print(count)
    # print(b[i])
    x=(b[i]-avl.search_lower(b[i],None))*(avl.search_higher(b[i],None)-b[i])*a[b[i]]
    count+=x
    # print(x)
    avl.insert(b[i])
    # avl.debug()
print(count)




Fixed submission:
#!/usr/bin/env python3
class UnionFind:
    __slots__ = ['id','sz']

    def __init__(self, n):
        self.id = [-1] * n

    def root(self, x):
        if self.id[x] < 0:
            return x
        else:
            self.id[x] = self.root(self.id[x])
            return self.id[x]

    def find(self, x, y):
        return uf.root(x) == uf.root(y)

    def union(self, x, y):
        s1, s2 = self.root(x), self.root(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            return True
        return False

n = int(input())
a = list(map(int,input().split()))
uf = UnionFind(n)
ans=0
data=[0]*n
b=[0]*(n+1)
for i in range(n):
    b[a[i]]=i
for i in range(n,0,-1):
    r,l=0,0
    data[b[i]]=i
    if b[i]+1 <= n-1:
        if data[b[i]+1]>0:
            uf.union(b[i],b[i]+1)
    r=-uf.id[uf.root(b[i])]

    if b[i]-1>=0 and data[b[i]-1]>0:
        uf.union(b[i],b[i]-1)
    l=1-uf.id[uf.root(b[i])]-r
    ans+=(r*l)*i
print(ans)