Buggy python submission (verdict: Time Limit Exceeded):
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 search1(self,key):#key以下の値で最大のものを出力（ない場合は-1）
        ans=-1
        if self.key==None:
            return None
        if self.key>key:
            if self.left==None:
                return ans
            else:
                return max(ans,self.left.search1(key))
        if self.key<key:
            if self.right==None:
                return max(ans,self.key)
            else:
                return max(ans,self.right.search1(key),self.key)
        return self.key

    def search2(self,key):#key以上の値で最小のものを出力（ない場合は10**20）
        ans=10**20
        if self.key==None:
            return None
        if self.key>key:
            if self.left==None:
                return min(ans,self.key)
            else:
                return min(ans,self.left.search2(key),self.key)
        if self.key<key:
            if self.right==None:
                return ans
            else:
                return min(ans,self.right.search2(key))
        return self.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())
A=list(map(int,input().split()))
A=[A[i]-1 for i in range(0,N)]
function=[0 for i in range(0,N)]
for i in range(0,N):
    function[A[i]]=i

checked=Avltree()
checked.insert(function[0])
data1=[0 for i in range(0,N)]
data2=[0 for i in range(0,N)]
data1[0]=-1
data2[0]=N
for i in range(1,N):
    if checked.search1(function[i])!=-1:
        data1[i]=checked.search1(function[i])
    else:
        data1[i]=-1
    if checked.search2(function[i])!=10**20:
        data2[i]=checked.search2(function[i])
    else:
        data2[i]=N
    checked.insert(function[i])

ans=0
for i in range(0,N):
    prod=(function[i]-data1[i])*(data2[i]-function[i])
    ans+=prod*(i+1)

print(ans)


Fixed submission:
import random
import time
# Treap

# d = 0: right rotation
# d = 1: left rotation
def rotate(nd, d):
    c = nd[d]
    if d:
        e = c[1]
        nd[1] = c[0]
        c[0] = nd
    else:
        e = c[0]
        nd[0] = c[1]
        c[1] = nd

    r = c[4] = nd[4]
    nd[4] = r - (e[4] if e else 0) - 1
    return c

# insert a node with key = val and priority = pri
root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]

    # [<left>, <right>, <key>, <priority>, <count>]
    nd = [None, None, val, pri, 1]
    while st:
        x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] += 1
        if x[3] >= nd[3]:
            break
        rotate(x, d)
    else:
        root = nd

    for x in st:
        x[4] += 1

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] -= 1
    return x

def delete(val):
    global root
    x = root

    st = []
    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        st.append(y)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
        for x in st:
            x[4] -= 1
    else:
        root = __delete(x)

def find(val):
    global root
    x = root
    while x:
        if val == x[2]:
            return 1
        x = x[x[2] < val]
    return 0

def search1(val):
    global root
    x = root
    ans=-1
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            ans=max(ans,x[2])
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans

def search2(val):
    global root
    x=root
    ans=10**20
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            ans=min(ans,x[2])
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans



N=int(input())
A=list(map(int,input().split()))
A=[A[i]-1 for i in range(0,N)]
function=[0 for i in range(0,N)]
for i in range(0,N):
    function[A[i]]=i

random.seed()
randint=random.randint

insert(function[0],randint(1,200000))
data1=[0 for i in range(0,N)]
data2=[0 for i in range(0,N)]
data1[0]=-1
data2[0]=N
for i in range(1,N):
    if search1(function[i])!=-1:
        data1[i]=search1(function[i])
    else:
        data1[i]=-1
    if search2(function[i])!=10**20:
        data2[i]=search2(function[i])
    else:
        data2[i]=N
    insert(function[i],randint(1,200000))

ans=0
for i in range(0,N):
    prod=(function[i]-data1[i])*(data2[i]-function[i])
    ans+=prod*(i+1)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
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 search1(self,key):#key以下の値で最大のものを出力（ない場合は-1）
        ans=-1
        if self.key==None:
            return None
        if self.key>key:
            if self.left==None:
                return ans
            else:
                return max(ans,self.left.search1(key))
        if self.key<key:
            if self.right==None:
                return max(ans,self.key)
            else:
                return max(ans,self.right.search1(key),self.key)
        return self.key

    def search2(self,key):#key以上の値で最小のものを出力（ない場合は10**20）
        ans=10**20
        if self.key==None:
            return None
        if self.key>key:
            if self.left==None:
                return min(ans,self.key)
            else:
                return min(ans,self.left.search2(key),self.key)
        if self.key<key:
            if self.right==None:
                return ans
            else:
                return min(ans,self.right.search2(key))
        return self.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())
A=list(map(int,input().split()))
A=[A[i]-1 for i in range(0,N)]
function=[0 for i in range(0,N)]
for i in range(0,N):
    function[A[i]]=i

checked=Avltree()
checked.insert(function[0])
data1=[0 for i in range(0,N)]
data2=[0 for i in range(0,N)]
data1[0]=-1
data2[0]=N
for i in range(1,N):
    if checked.search1(function[i])!=-1:
        data1[i]=checked.search1(function[i])
    else:
        data1[i]=-1
    if checked.search2(function[i])!=10**20:
        data2[i]=checked.search2(function[i])
    else:
        data2[i]=N
    checked.insert(function[i])

ans=0
for i in range(0,N):
    prod=(function[i]-data1[i])*(data2[i]-function[i])
    ans+=prod*(i+1)

print(ans)


Fixed submission:
import random
import time
# Treap

# d = 0: right rotation
# d = 1: left rotation
def rotate(nd, d):
    c = nd[d]
    if d:
        e = c[1]
        nd[1] = c[0]
        c[0] = nd
    else:
        e = c[0]
        nd[0] = c[1]
        c[1] = nd

    r = c[4] = nd[4]
    nd[4] = r - (e[4] if e else 0) - 1
    return c

# insert a node with key = val and priority = pri
root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]

    # [<left>, <right>, <key>, <priority>, <count>]
    nd = [None, None, val, pri, 1]
    while st:
        x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] += 1
        if x[3] >= nd[3]:
            break
        rotate(x, d)
    else:
        root = nd

    for x in st:
        x[4] += 1

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] -= 1
    return x

def delete(val):
    global root
    x = root

    st = []
    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        st.append(y)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
        for x in st:
            x[4] -= 1
    else:
        root = __delete(x)

def find(val):
    global root
    x = root
    while x:
        if val == x[2]:
            return 1
        x = x[x[2] < val]
    return 0

def search1(val):
    global root
    x = root
    ans=-1
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            ans=max(ans,x[2])
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans

def search2(val):
    global root
    x=root
    ans=10**20
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            ans=min(ans,x[2])
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans



N=int(input())
A=list(map(int,input().split()))
A=[A[i]-1 for i in range(0,N)]
function=[0 for i in range(0,N)]
for i in range(0,N):
    function[A[i]]=i

random.seed()
randint=random.randint

insert(function[0],randint(1,200000))
data1=[0 for i in range(0,N)]
data2=[0 for i in range(0,N)]
data1[0]=-1
data2[0]=N
for i in range(1,N):
    if search1(function[i])!=-1:
        data1[i]=search1(function[i])
    else:
        data1[i]=-1
    if search2(function[i])!=10**20:
        data2[i]=search2(function[i])
    else:
        data2[i]=N
    insert(function[i],randint(1,200000))

ans=0
for i in range(0,N):
    prod=(function[i]-data1[i])*(data2[i]-function[i])
    ans+=prod*(i+1)

print(ans)