Problem:


Score : 400 points

Problem Statement

One day, Snuke was given a permutation of length N, a_1, a_2, ..., a_N, from his friend.

Find the following:

Constraints

1 ≦ N ≦ 200,000

(a_1, a_2, ..., a_N) is a permutation of (1, 2, ..., N).

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the answer.

Note that the answer may not fit into a 32-bit integer.

Sample Input 1

3
2 1 3

Sample Output 1

9

Sample Input 2

4
1 3 2 4

Sample Output 2

19

Sample Input 3

8
5 4 8 1 2 6 7 3

Sample Output 3

85



Sample input:
3
2 1 3


Sample output:
9

Submission status: Time Limit Exceeded

Solution code:
#https://tjkendev.github.io/procon-library/python/range_query/rmq_segment_tree.html
# N: 処理する区間の長さ

N = int(input())
N+=1
a = [-1]+list(map(int, input().split( )))


N0 = 1
while N0<=N:
    N0*=2
INF = 10**10
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1],data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s,data[R-1])

        if L & 1:
            s = min(s,data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
for i in range(N):
    update(i,a[i])
anss = 0
for i in range(1,N):
    ans = a[i]
    mx = N
    mn = i
    while mx-mn>1:
        md = (mx+mn)//2
        aj = query(i,md+1)
        if aj==a[i]:
            mn = md
        else:
            mx = md
    tmp = mn-i+1
    ans *= mn-i+1
    mn = 0
    mx = i
    while mx-mn>1:
        md = (mx+mn)//2
        aj = query(md,i+1)
        if aj==a[i]:
            mx = md
        else:
            mn = md
    ans*=i-mx+1
    anss+=ans
print(anss)

Submission status: Time Limit Exceeded

Solution code:
#https://tjkendev.github.io/procon-library/python/range_query/rmq_segment_tree.html
# N: 処理する区間の長さ

#bit管理
#演算はor
N = int(input())
N+=1
a = [-1]+list(map(int, input().split( )))


N0 = 1
while N0<=N:
    N0*=2
INF = 10**10
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1],data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s,data[R-1])

        if L & 1:
            s = min(s,data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
for i in range(N):
    update(i,a[i])
anss = 0
for i in range(1,N):
    ans = a[i]
    mx = N
    mn = i
    while mx-mn>1:
        md = (mx+mn)//2
        aj = query(i,md+1)
        if aj==a[i]:
            mn = md
        else:
            mx = md
    tmp = mn-i+1
    ans *= mn-i+1
    mn = 0
    mx = i
    while mx-mn>1:
        md = (mx+mn)//2
        aj = query(md,i+1)
        if aj==a[i]:
            mx = md
        else:
            mn = md
    ans*=i-mx+1
    anss+=ans
print(anss)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())
A = list(map(int, input().split()))

idx = [0] * (N+1)
for i in range(N):
    a = A[i]
    idx[a] = i


class SegmentTree:
    """
    引数：
        N: 処理する区間の長さ
        operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
        UNIT: 単位元
        a: 長さNの配列 a で初期化（a を与えない場合、単位元で初期化）
    注意: 内部的には 1-indexed
    """

    def __init__(self, N, operator, unit, a=None):
        self.op = operator
        self.UNIT = unit

        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.UNIT]*(2*self.N0)
        if a != None:
            self.tree[self.N0:self.N0+N] = a[:]
            for k in range(self.N0-1, 0, -1):
                self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])

    # a_k の値を x に更新
    def update(self, k, x):
        k += self.N0
        self.tree[k] = x
        k //= 2
        while k:
            self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
            k //= 2

    # 区間[l,r)をopでまとめる
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = self.UNIT
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(self.tree[R], s)
            if L & 1:
                s = self.op(s, self.tree[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get(self, k):  # k番目の値を取得。query[k,k]と同じ
        return self.tree[k + self.N0]

    def all(self):
        return self.tree[1]


seg_sml = SegmentTree(N, min, N)
seg_big = SegmentTree(N, max, -1)

ans = 0

for a in range(1, N + 1):
    i = idx[a]
    l = seg_big.query(0, i)
    r = seg_sml.query(i, N)

    left = i - l - 1
    right = r - i - 1

    cnt = (r - l - 1) * (r - l) // 2
    cnt -= left * (left + 1) // 2
    cnt -= right * (right + 1) // 2

    ans += cnt * a

    seg_sml.update(i, i)
    seg_big.update(i, i)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
D = {A[i]: i for i in range(N)}
X = [0 for i in range(N)]
S = 0
for i in range(1, N+1):
  if i == 1:
    S += (D[i] + 1) * (N - D[i])
    X[D[i]] = 1
  else:
    left, right = D[i], D[i]
    while left != -1:
      left -= 1
      if left == -1:
        break
      else:
        if X[left] == 1:
          break
    while right != N:
      right += 1
      if right == N:
        break
      else:
        if X[right] == 1:
          break
    S += i * (D[i] - left) * (right - D[i])
    X[D[i]] = 1
print(S)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
import bisect
 
def main():
    N = int(input())
    a = list(map(int,input().split()))
    
    pos = [-1 for _ in range(N)]
    for i,num in enumerate(a):
        pos[num-1] = i

    ins,count = [-1,N],0
    for i,num in enumerate(pos):
        ind = bisect.bisect_left(ins,num)
        bisect.insort(ins,num)
        l,r = ins[ind]-ins[ind-1],ins[ind+1]-ins[ind]
        count += (i+1)*(r*l)
    
    print(count)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

#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())
A = [int(i) for i in input().split()]

IDX = defaultdict(int)
for idx,a in enumerate(A):
    IDX[a] = idx + 1

# AVL木の初期化
avl_key = [0]
avl_left = [None] * (N + 2)
avl_right = [None] * (N + 2)
balance = [0] * (N + 2)
insert(0, N + 1)

ans = 0
for n in range(1, N + 1):
    insert(0, IDX[n])
    H = search_higher(0, IDX[n], None)
    L = search_lower(0, IDX[n], None)
    ans += (IDX[n] - L) * (H - IDX[n]) *  n

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left
from collections import defaultdict

def main():
    N = int(input())
    A = [int(i) for i in input().split()]

    # IDX[n]: nのindex
    IDX = defaultdict(int)
    for idx,a in enumerate(A):
        IDX[a] = idx

    ans = 0
    T = [-1, N]
    for n in range(1, N + 1):
        idx = bisect_left(T, IDX[n])
        T = T[:idx] + [IDX[n]] + T[idx:]
        ans += (T[idx] - T[idx-1]) * (T[idx+1] - T[idx]) * n

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from bisect import insort_left, bisect_left
from collections import defaultdict

def main():
    N = int(input())
    A = [int(i) for i in input().split()]

    # IDX[n]: nのindex
    IDX = defaultdict(int)
    for idx,a in enumerate(A):
        IDX[a] = idx

    ans = 0
    T = [-1, N]
    for n in range(1, N + 1):
        insort_left(T, IDX[n])
        idx = bisect_left(T, IDX[n])
        ans += (T[idx] - T[idx-1]) * (T[idx+1] - T[idx]) * n

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort_left, bisect_left
from collections import defaultdict

N = int(input())
A = [int(i) for i in input().split()]

N_IDX = defaultdict(int)
for idx,a in enumerate(A):
    N_IDX[a] = idx

ans = 0
T = [-1, N]
for n in range(1, N + 1):
    insort_left(T, N_IDX[n])
    idx = bisect_left(T, N_IDX[n])
    ans += (T[idx] - T[idx-1]) * (T[idx+1] - T[idx]) * n

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n=int(input())
n+=3
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num

l=list(map(int,input().split()))
p=[]

n-=3
for i in range(n):
    p.append([l[i],i+1])
p.sort(key=lambda x:x[0])
ans=0
update(0,1)
update(n+1,1)
for i in range(n):
    update(p[i][1],1)
    x=query(0,p[i][1]+1)
    ok=n+2
    ng=-1
    while ok-ng>1:
        m=(ok+ng)//2
        if query(0,m)<x-1:
            ng=m
        else:
            ok=m
    left=ok
    
    ok=n+2
    ng=-1
    while ok-ng>1:
        m=(ok+ng)//2
        if query(0,m)<x+1:
            ng=m
        else:
            ok=m
    right=ng
    ans+=(i+1)*(p[i][1]-left+1)*(right-p[i][1])
    #print(left,p[i][1],right)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n=int(input())
n+=3
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num

l=list(map(int,input().split()))
p=[]

n-=3
for i in range(n):
    p.append([l[i],i+1])
p.sort(key=lambda x:x[0])
ans=0
update(0,1)
update(n+1,1)
for i in range(n):
    update(p[i][1],1)
    x=query(0,p[i][1]+1)
    ok=n+2
    ng=-1
    while ok-ng>1:
        m=(ok+ng)//2
        if query(0,m)<x-1:
            ng=m
        else:
            ok=m
    left=ok
    
    ok=n+2
    ng=-1
    while ok-ng>1:
        m=(ok+ng)//2
        if query(0,m)<x+1:
            ng=m
        else:
            ok=m
    right=ng
    ans+=(i+1)*(p[i][1]-left+1)*(right-p[i][1])
    #print(left,p[i][1],right)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#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())
nn=n+1
l=list(map(int,input().split()))
li=[]
for i in range(n):
    li.append([l[i],i+1])
li.sort()

avl_key = [0]
avl_left = [None]*nn
avl_right = [None]*nn
balance = [0]*nn
ans=0

for i in range(n):
    insert(0,li[i][1])
    
    left = search_lower(0,li[i][1],None)
    right = search_higher(0,li[i][1],None)
    if not right:
        right=n
    else:
        right-=1
    if left==0:
        left=1
    else:
        left+=1
    ans+=(i+1)*(li[i][1]-left+1)*(right-li[i][1]+1)
    #print(left,right,li[i][1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)