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:
n=int(input())
ide_ele=n
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
segfunc=min

def init(init_val):
  for i in range(n):
    seg[i+num-1]=init_val[i]    
    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
init_val=[int(i) for i in input().split()]
init(init_val)
ans=0
for i in range(n):
  for j in range(i,n):
    ans+=query(i,j+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_lst = list(map(int, input().split()))


ans = 0
for i in range(N):
    value = a_lst[i]
    l, r = i + 1, N - i
    for j in range(i, -1, -1):
        if a_lst[j] < value:
            l = i - j
            break

    for j in range(i+1, N):
        if a_lst[j] < value:
            r = j - i
            break

    ans += value*l*r

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_lst = list(map(int, input().split()))


#print()

ans = 0
for i in range(N):
    value = a_lst[i]
    l, r = 1, 1
    for j in range(i, -1, -1):
        if a_lst[j] < value:
            l = i - j
            break
        if j == 0:
            l = i + 1

    for j in range(i+1, N):
        if a_lst[j] < value:
            r = j - i
            break
        if j == N - 1:
            r = N - i

#    print(value, l, r, i)
    ans += value*l*r

#print()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0] + list(map(int, input().split())) + [0]
ans = 0
for i in range(1,n+1):
  l,r = i,i
  while a[l-1] > a[i]:
    l -= 1
  while a[r+1] > a[i]:
    r += 1
  ans += a[i]*(i-l+1)*(r-i+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0] + list(map(int, input().split())) + [0]
ans = 0
for i in range(1,n+1):
  l,r = i,i
  while a[l-1] > a[i]:
    l -= 1
  while a[r+1] > a[i]:
    r += 1
  ans += a[i]*(i-l+1)*(r-i+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numpy import*
n,*a=map(int,open(0).read().split())
l=[0]*n
for i,v in enumerate(a,1):
  l[v-1]=i
b=array([0,n+1])
c=0
for i,v in enumerate(l,1):
  j=searchsorted(b,v)
  c+=(b[j]-v)*(v-b[j-1])*i
  b=union1d(b,[v])
print(c)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split()))
B=[i+1 for i in range(N)]

C=[]
for i in range(N):
    C.append([A[i],B[i]])
C.sort()

L=[0,N+1]

ans=0

#print(C)
for i in range(N):
    ans+=C[i][0]*(L[bisect.bisect_right(L,C[i][1])]-C[i][1])*(C[i][1]-L[bisect.bisect_left(L,C[i][1])-1])
    L.insert(bisect.bisect_left(L,C[i][1]),C[i][1])
    #print(ans,L)
#print(L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))

ans = 0
for i in range(n):
    s = 0
    e = n-1
    for j in range(i):
        if a[i]>a[i-j-1]:
            s = i-j
            break
    for j in range(i+1,n):
        if a[i]>a[j]:
            e = j-1
            break
    ans += (i-s+1)*(e-i+1)*a[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**5)

n = int(input())
a = list(map(int, input().split()))
# aのindexを前計算
d = {}
for i,j in enumerate(a):
    d[j] = i


# segtree
data = [float("inf")]*(2*n)
# a_k の値を x に更新
def update(k, x):
    k += n-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 + n; R = r + n
    s = float("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

# initialize
for i, j in enumerate(a):
    update(i,j)

# 区間[left, right)が与えられた場合の和を求める再帰
def rec(left=0, right=n):
    if left==right:
        return 0
    # O(logN)
    min_ = query(left, right)
    ind = d[min_]
    res = min_*(right-ind)*(ind+1-left)
    res += rec(left, ind)
    res += rec(ind+1,right)
    return res

print(rec())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**5)

n = int(input())
a = list(map(int, input().split()))
# aのindexを前計算
d = {}
for i,j in enumerate(a):
    d[j] = i


# segtree
data = [float("inf")]*(2*n)
# a_k の値を x に更新
def update(k, x):
    k += n-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 + n; R = r + n
    s = float("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

# initialize
for i, j in enumerate(a):
    update(i,j)

# 区間[left, right)が与えられた場合の和を求める再帰
def rec(left=0, right=n):
    if left==right:
        return 0
    min_ = query(left, right)
    ind = d[min_]
    res = min_*(right-ind)*(ind+1-left)
    res += rec(left, ind)
    res += rec(ind+1,right)
    return res

print(rec())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
input()
def f(s):
    if len(s)==0:
        return 0
    k=len(s)
    g=np.argmin(s)
    return s[g]*(g+1)*(k-g)+f(s[:g])+f(s[g+1:])
print(f(list(map(int,input().split()))))

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
n,*a=map(int,open(0).read().split())
l=[0]*n
for i,v in enumerate(a,1):
  l[v-1]=i
b=[0,n+1]
c=0
for i,v in enumerate(l,1):
  j=bisect(b,v)
  c+=(b[j]-v)*(v-b[j-1])*i
  b.insert(j,v)
print(c)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
a = list(map(int, input().split()))
b = [0] * (N + 1)
for i in range(N):
    b[a[i]] = i + 1
c = [0, N + 1]
ans = 0
for i in range(1, N + 1):
    m = b[i]
    x = bisect.bisect(c, m)
    y = c[x - 1]
    z = c[x]
    ans += (((z - y) * (z - y - 1) - (m - y) * (m - y - 1) - (z - m) * (z - m - 1)) // 2) * i
    bisect.insort(c, m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
a = list(zip(list(map(int, input().split())), range(1, N + 1)))
b = [0, N + 1]
a.sort()
ans = 0
for j, i in a:
    x = bisect.bisect(b, i)
    y = b[x - 1]
    z = b[x]
    ans += (((z - y) * (z - y - 1) - (i - y) * (i - y - 1) - (z - i) * (z - i - 1)) // 2) * j
    bisect.insort(b, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = 1000000007

class RMQ:
    def __init__(self, n):
        _n = 1
        while _n < n:
            _n <<= 1
        self.n = _n
        self.dat = [INF] * (2 * _n - 1)

    def update(self, k, x):
        k += self.n - 1
        self.dat[k] = x
        while k > 0:
            k = (k - 1) >> 1
            self.dat[k] = min(self.dat[2 * k + 1], self.dat[2 * k + 2])

    def __query(self, s, t, k, l, r):
        if r <= s or t <= l:
            return INF
        if s <= l and r <= t:
            return self.dat[k]

        mid = (l + r) >> 1
        vl = self.__query(s, t, 2 * k + 1, l, mid)
        vr = self.__query(s, t, 2 * k + 2, mid, r)
        return min(vl, vr)

    def query(self, s, t):
        return self.__query(s, t, 0, 0, self.n)

def main():
    n = int(input())
    a = [int(s) for s in input().split()]
    rmq = RMQ(n)
    for i, x in enumerate(a):
        rmq.update(i, x)

    print(sum(sum(rmq.query(l, r + 1) for r in range(l, n)) for l in range(n)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A):
        idxs[a] = i
    def func(l, r):
        if l == r:
            return 0
        a = min(A[l:r])
        idx = idxs[a]
        area = (idx + 1 - l) * (r - idx) * a
        return area + func(l, idx) + func(idx + 1, r)
    ans = func(0, N)

    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter
from bisect import bisect_right

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A, 1):
        idxs[a] = i
    lowers = [0, N + 1]
    ans = 0
    for a, i in enumerate(idxs[1:], 1):
        j = bisect_right(lowers, i)
        l, r = lowers[j - 1], lowers[j]
        lowers = lowers[:j] + [i] + lowers[j:]
        ans += (i - l) * (r - i) * a

    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter
from bisect import bisect_right

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A, 1):
        idxs[a] = i
    lowers = [0, N + 1]
    ans = 0
    for a, i in enumerate(idxs[1:], 1):
        j = bisect_right(lowers, i)
        l, r = lowers[j - 1], lowers[j]
        lowers.insert(j, i)
        ans += (i - l) * (r - i) * a

    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter

def main():
    N = II()
    A = LI()
    def func(arr):
        if len(arr) == 0:
            return 0
        a = min(arr)
        idx = arr.index(a)
        return (idx + 1) * (len(arr) - idx) * a + func(arr[:idx]) + func(arr[idx + 1:])
    ans = func(A)

    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
  l,r = 1,1
  while i-l > -1 and a[i-l] > a[i]:
    l += 1
  while i+r < n and a[i+r] > a[i]:
    r += 1
  ans += l*r*a[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
li = [int(i) for i in input().split()]

ans = 0
for i in range(N):
    for j in range(i,N):
        if i < j:
            ans += min(li[i:j+1])
        elif i == j:
            ans += li[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    #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 = 200002
    avl_key = [0]
    avl_left = [None]*n
    avl_right = [None]*n
    balance = [0]*n


    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):
        l[v-1]=i
    insert(0,0)
    insert(0,n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(0,v,None)-v)*(v-search_lower(0,v,None))*i
        insert(0,v)
    print(c)
if __name__=='__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    #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 = 200002
    avl_key = [0]
    avl_left = [None]*n
    avl_right = [None]*n
    balance = [0]*n


    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):
      l[v-1]=i
    insert(0,0)
    insert(0,n+1)
    c=0
    for i,v in enumerate(l,1):
      c+=(search_higher(0,v,None)-v)*(v-search_lower(0,v,None))*i
      insert(0,v)
    print(c)
if __name__=='__main__':
    solve()