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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:

    def __init__(self, n):
        
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """
    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok


def calc1(m):
    cnt = lend - bit.sum(m-1)
    return cnt == 0


def calc2(m):
    cnt = bit.sum(m) - rstart
    return cnt == 0

N = INT()
A = LIST()

idxs = [0] * (N+1)
for i, a in enumerate(A):
    idxs[a] = i + 1

bit = BIT(N+2)

bit.add(0, 1)
bit.add(N+1, 1)
ans = [0] * (N+1)
for a in range(1, N+1):
    
    idx = idxs[a]
    
    lend = bit.sum(idx)
    rstart = bit.sum(idx-1)
    
    l = bisearch_min(0, idx+1, calc1)
    
    r = bisearch_max(idx, N+1, calc2)
    
    ans[a] = (idx-l+1) * (r-idx+1) * a
    
    bit.add(idx, 1)

print(sum(ans))

Solution (Python):
n=int(input())
a=[int(j) for j in input().split()]
ans=0
l=list(range(n+2))
r=list(range(n+2))

index=[0]*(n+1)
for i in range(n):
    index[a[i]]=i

for i in range(1,n+1)[::-1]:
    ind=index[i]
    x,y=l[ind],r[ind]
    ans+=i*(ind-x+1)*(y-ind+1)
    l[y+1],r[x-1]=x,y
print(ans)

Solution (Python):
N=int(input())
a=[0]+[int(i) for i in input().split()]
par=[0 for i in range(N+1)]
size=[0 for i in range(N+1)]
def find(x):
    if (par[x]==x):
        return x
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    res=size[x]*size[y]
    size[x]+=size[y]
    par[y]=x
    return res
for i in range(N+1):
    par[i]=i
    size[i]=1
b=[0 for i in range(N+1)]
for i in range(N+1):
    b[a[i]]=i
ans=0
for j in range(1,N+1)[::-1]:
    i=b[j]
    ans+=a[i]
    if i-1>=1 and a[i-1]>a[i]:
        ans+=unite(i-1,i)*a[i]
    if i+1<=N and a[i+1]>a[i]:
        ans += unite(i+1,i)*a[i]
print(ans)

Solution (Python):
root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)

Solution (Python):
root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)

Solution (Python):
class SparseTable():
    def __init__(self, array, n):
        '''テーブルを構築する'''
        self.row_size = n.bit_length()

        
        
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1

        
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
               self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                                       self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        '''クエリの内容'''
        return min(num1, num2)

    def query(self, l, r):
        '''区間[l, r)に対するクエリに答える'''
        if r == l:
            return None
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])
  
n = int(input())
a = list(map(int, input().split()))
st = SparseTable(a, n)
ans = 0
for i in range(n):
    ok = i + 1
    ng = n + 1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if st.query(ok, mid) < a[i]:
            ng = mid
        else:
            ok = mid
    tmp1 = ok - i - 1
    
    ok = i
    ng = -1
    mid = (ok + ng) // 2
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if st.query(mid, i + 1) < a[i]:
            ng = mid
        else:
            ok = mid
    tmp2 = i - ok
    ans += ((tmp1+1) * (tmp2+1))* a[i]
print(ans)

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def sol():
    N = int(input())
    A = [int(x) for x in input().split()]

    indexList = {x : i for i, x in enumerate(A)}

    V = set()
    rootList = {}
    size = {}

    def getRoot(index):
        parent = rootList[index]
        if parent == index:
            return index
        root = getRoot(parent)
        rootList[index] = root
        return root

    def union(x, y):
        rootX, rootY = getRoot(x), getRoot(y)
        sX, sY = size[rootX], size[rootY]
        if sX > sY:
            sX, sY = sY, sX
            rootX, rootY = rootY, rootX
        rootList[rootX] = rootY
        size[rootY] += sX

    ans = 0
    for x in range(N, 0, -1):
        index = indexList[x]
        V.add(index)
        size[index] = 1
        rootList[index] = index
        left, right = 0, 0

        if index - 1 in V:
            left = size[getRoot(index - 1)]
            union(index, index - 1)
        if index + 1 in V:
            right = size[getRoot(index + 1)]
            union(index, index + 1)

        count = (left + 1) * (right + 1)
        ans += x * count

    print(ans)


sol()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)




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

x_to_i = {x:i for i,x in enumerate(A)}

V = set()
root = dict()
size = dict()

def find_root(x):
    y = root[x]
    if x == y:
        return y
    ry = find_root(y)
    root[x] = ry
    return ry

def merge(x,y):
    rx = find_root(x)
    ry = find_root(y)
    sx = size[rx]
    sy = size[ry]
    if sx > sy:
        rx,ry = ry,rx
        sx,sy = sy,sx
    root[rx] = ry
    size[ry] += sx

answer = 0
for x in range(N,0,-1):
    i = x_to_i[x]
    V.add(i)
    size[i] = 1
    root[i] = i
    left = 0
    right = 0
    if i-1 in V:
        left = size[find_root(i-1)]
        merge(i-1,i)
    if i+1 in V:
        right = size[find_root(i+1)]
        merge(i+1,i)
    cnt = (left+1) * (right+1)
    answer += x * cnt

print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def getSize(self, x):
        return self.size[self.find(x)]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

N = int(input())
A = list(map(int, input().split()))
B = [-1] * (N+1)
for i, a in enumerate(A):
    B[a] = i
uf = UnionFind(N)
ans = 0
for x in range(N, 0, -1):
    i, l, r = B[x], 0, 0
    if 0 < i and A[i] < A[i-1]:
        l = uf.getSize(i-1)
        uf.unite(i-1, i)
    if i < N-1 and A[i] < A[i+1]:
        r = uf.getSize(i+1)
        uf.unite(i, i+1)
    ans += (l+1)*(r+1)*x
print(ans)

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

pos = [0] * (N + 1)
pos[0] = -1
for i, a in enumerate(A):
    pos[a] = i

ans = 0
lefts = [0] * N
rights = [0] * N
for i in reversed(range(1, N + 1)):
    p = pos[i]
    if p + 1 < N and A[p + 1] > i:
        
        right = rights[p + 1]
    else:
        right = p
    if p - 1 >= 0 and A[p - 1] > i:
        
        left = lefts[p - 1]
    else:
        left = p
    lefts[right] = left
    rights[left] = right
    ans += (p - left + 1) * (right - p + 1) * i
print(ans)

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

pos = [0] * (N + 1)
pos[0] = -1
for i, a in enumerate(A):
    pos[a] = i

ans = 0
lefts = [0] * N
rights = [0] * N
for i in reversed(range(1, N + 1)):
    p = pos[i]
    if p + 1 < N and A[p + 1] > i:
        
        right = rights[p + 1]
    else:
        right = p
    if p - 1 >= 0 and A[p - 1] > i:
        
        left = lefts[p - 1]
    else:
        left = p
    lefts[right] = left
    rights[left] = right
    ans += (p - left + 1) * (right - p + 1) * i
print(ans)

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def gutyocu():
    ans = 0
    for i, j in itertools.combinations_with_replacement(range(N), r=2):
        ans += min(A[i: j + 1])
    return ans


pos = list(range(N + 1))
pos[0] = -1
for i, a in enumerate(A):
    pos[a] = i

ans = 0
lefts = list(range(N + 1))
rights = list(range(N + 1))
for i in reversed(range(1, N + 1)):
    p = pos[i]
    if p + 1 < N and A[p + 1] > i:
        
        right = rights[p + 1]
    else:
        right = p
    if p - 1 >= 0 and A[p - 1] > i:
        
        left = lefts[p - 1]
    else:
        left = p
    lefts[right] = left
    rights[left] = right
    ans += (abs(left - p) + 1) * (abs(right - p) + 1) * i
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a=sorted(list(enumerate(a)),key=lambda x:x[1])

l=1
while l<2*(n+2)-1:
	l*=2
l-=1
seg=[True]*l
seg[0]=False

def update(i):
	if seg[i]:
		seg[i]=False
		update((i-1)//2)

update((l-1)//2)
update((l-1)//2+n+1)

def search_left(i,j):
	if j==1:
		if i%2==1:
			return search_left((i-1)//2,1)
		else:
			if seg[i-1]:
				return search_left((i-1)//2,1)
			else:
				return search_left(i-1,0)
	else:
		if i<l//2:
			return search_left(2*i+2-seg[2*i+2],0)
		else:
			return i

def search_right(i,j):
	if j==1:
		if i%2==0:
			return search_right((i-1)//2,1)
		else:
			if seg[i+1]:
				return search_right((i-1)//2,1)
			else:
				return search_right(i+1,0)
	else:
		if i<l//2:
			return search_right(2*i+1+seg[2*i+1],0)
		else:
			return i

ans=0
for i,j in a:
	s=(l//2+1+i)
	p=search_left(s,1)
	q=search_right(s,1)
	ans+=(s-p)*(q-s)*j
	update(s)

print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
p=[None]*N
for i,a in enumerate(A):
    p[a-1]=i
ans=0
l,r=[i for i in range(N)],[i for i in range(N)]
for i in range(N-1,-1,-1):
    left,right=l[p[i]],r[p[i]]
    ans+=(i+1)*(p[i]-left+1)*(right-p[i]+1)
    if left>0:
        r[left-1]=right
    if right<N-1:
        l[right+1]=left
print(ans)

Solution (Python):

import sys


def solve(N: int, a: "List[int]"):
    idx = {aa: i for i, aa in enumerate(a)}
    left = [i for i in range(N+2)]
    right = [i for i in range(N+2)]
    res = 0
    for n in range(N, 0, -1):
        i = idx[n]
        l = left[i]
        r = right[i]
        res += n * (i - l + 1) * (r - i + 1)
        left[r+1] = l
        right[l-1] = r
    print(res)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, a)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
a = list(map(int, input().split()))

b = [0] * (N + 1)
l = [i for i in range(N + 2)]
r = [i for i in range(N + 2)]

ans = 0
for i in range(N):
    b[a[i]] = i 

for i in range(N, 0, -1):
    m = b[i] 
    x, y = l[m], r[m] 
    ans += i * (m - x + 1) * (y - m + 1) 
    l[y + 1], r[x - 1] = x, y 

print (ans)

Solution (Python):
N = int(input())
*A, = map(int,input().split())

P = [0]*N
for i,a in enumerate(A):
    P[a-1] = i

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
        self.Min = [-1]*N
        self.Max = [-1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def get_min(self,n):
        p = self.get_Parent(n)
        return self.Min[p]
    def get_max(self,n):
        p = self.get_Parent(n)
        return self.Max[p]
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y: 
            self.Min[x] = min(self.Min[x],self.Min[y])
            self.Max[x] = max(self.Max[x],self.Max[y])
            self.Parent[y] = x
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)
    def create(self,n):
        if self.Min[n] == -1:
            self.Min[n] = n
            self.Max[n] = n

T = UnionFind(N)
ans = 0
for i in range(N-1,-1,-1):
    p = P[i]
    T.create(p)
    if p-1>=0 and T.get_min(p-1)!=-1:
        T.merge(p,p-1)
    if p+1<N and T.get_min(p+1)!=-1:
        T.merge(p,p+1)
    ans += (i+1)*(p-T.get_min(p)+1)*(T.get_max(p)-p+1)
print(ans)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    pos = [-1] * (N+1)
    for i in range(N):
        pos[A[i]] = i
    left = list(range(N+2))
    right = list(range(N+2))
    ans = 0
    for i in range(N, 0, -1):
        p = pos[i]
        l = left[p]
        r = right[p]
        ans += i * (p-l+1) * (r-p+1)
        left[r+1] = left[p]
        right[l-1] = right[p]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
*A, = map(int, input().split())
indices = {a: i for i, a in enumerate(A)}
left = {i: i for i in range(N)} 
right = {i: i for i in range(N)} 
ans = 0
for a in range(N, 0, -1):
    idx = indices[a]
    l, r = left[idx], right[idx]
    ans += (idx - l + 1) * (r - idx + 1) * a
    left[r+1], right[l-1] = l, r 
print(ans)

Solution (Python):
n=int(input())
ans=0
arr=list(map(int,input().split()))
pos=[0]*(n+1)
for i in range(n):
  pos[arr[i]]=i
l=[i for i in range(n+1)]
r=[i for i in range(n+1)]
for i in range(n,0,-1):
  idx=pos[i]
  tl,tr=l[idx],r[idx]
  ans+=i*(idx-tl+1)*(tr-idx+1)
  l[tr+1]=tl
  r[tl-1]=tr
print(ans)

Solution (Python):
N = int(input())
a = list(map(int,input().split()))

b = [[a[i],i] for i in range(N)]
b.sort(key=lambda x:x[0],reverse=True)

lr = [[0,0] for i in range(N)]
ans = 0
for i in range(N):
    ans+=b[i][0]*(lr[b[i][1]][1]+1)*(lr[b[i][1]][0]+1)
    if b[i][1]+lr[b[i][1]][1]+1<N:
        lr[b[i][1]+lr[b[i][1]][1]+1][0] = lr[b[i][1]][0]+lr[b[i][1]][1]+1
    if b[i][1]-lr[b[i][1]][0]-1>-1:
        lr[b[i][1]-lr[b[i][1]][0]-1][1] = lr[b[i][1]][0]+lr[b[i][1]][1]+1


print(ans)

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

index = [-1] * (n + 1)
for i, v in enumerate(a):
    index[v] = i

area = [[i, i] for i in range(n + 1)]
result = 0
for i in range(n, 0, -1):
    position = index[i]
    l, r = area[position]
    area[r + 1][0] = l 
    area[l - 1][1] = r 
    result += (position - l + 1) * (r - position + 1) * i
print(result)

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
a = list(map(int,input().split()))
b = [0]*(N+1)
left,right = [i for i in range(N+2)],[i for i in range(N+2)]
ans = 0
for i in range(N):
    b[a[i]] = i
for i in range(N+1)[::-1]:
    m = b[i]
    l,r = left[m],right[m]
    ans += i*(m-l+1)*(r-m+1)
    left[r+1]=l
    right[l-1]=r
print(ans)

Solution (Python):
n=int(input())
A=[int(i) for i in input().split()]

Ans=[0]*n
Ans[0]=1
Stack=[[A[0],1]]
for i in range(1,n):
  a=A[i]
  b,ct_b=Stack.pop()
  ct=1
  while b>a and Stack:
    ct+=ct_b
    b,ct_b=Stack.pop()
  if b<a:
    Stack.append([b,ct_b])
    Stack.append([a,ct])
  else:
    Stack.append([a,ct+ct_b])
    ct+=ct_b
  Ans[i]=ct
RA=A[::-1]
Ans_R=[0]*n
Ans_R[0]=1
Stack=[[RA[0],1]]
for i in range(1,n):
  a=RA[i]
  b,ct_b=Stack.pop()
  ct=1
  while b>a and Stack:
    ct+=ct_b
    b,ct_b=Stack.pop()
  if b<a:
    Stack.append([b,ct_b])
    Stack.append([a,ct])
  else:
    Stack.append([a,ct+ct_b])
    ct+=ct_b
  Ans_R[i]=ct  
Ans_R=Ans_R[::-1]
ans=0
for i in range(n):
  ans+=(A[i]*Ans[i]*Ans_R[i])
print(ans)

Solution (Python):
import sys
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
class DammyMap:
    
    def __init__(self, A, B, issum = False):
        
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        if issum:
            self.sumtree = [0] * (self.size + 1)
            Ssum = [0] + list(accumulate([CA[self.X[i]]*self.X[i] for i in range(self.size)]))
            for i in range(1, 1+self.size):
                self.sumtree[i] = Ssum[i] - Ssum[i - (i&-i)]
    def compress(self, L):
        
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        
        return L2, C
    
    def leng(self):
        
        return self.count(self.size)
    
    def count(self, i):
        
        i = self.comp[i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        
        i = self.comp[i]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        
        
    def get(self, v):
        
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s]
            k //= 2
        return self.X[s]
    
    def addsum(self, i, x):
        
        x *= i
        i = self.comp[i]
        while i <= self.size:
            self.sumtree[i] += x
            i += i & -i
    
    def countsum(self, i):
        
        i = self.comp[i]
        s = 0
        while i > 0:
            s += self.sumtree[i]
            i -= i & -i
        return s
    
    def getsum(self, v):
        
        x = self.get(v)
        return self.countsum(x) - x*(self.count(x) - v)


N = int(input())
A = list(map(int, input().split()))
B = {v : i for i, v in enumerate(A, 1)}
T = DammyMap([0, N+1], list(range(0, N+2)))
ans = 0
for a in range(1, N+1):
    b = B[a]
    T.add(b, 1)
    i = T.count(b)
    ans += a*(T.get(i+1)-b)*(b-T.get(i-1))
print(ans)

Solution (Python):
N=int(input())
a=list(map(int,input().split()))

l=[]
r=[]
s=[]

for i,x in enumerate(a):
  left=i
  while len(s)>0 and x<s[-1][0]:
    left=s[-1][-1]
    s.pop()
  l.append(left)
  s.append([x,left])
  
  
s=[]
for i in range(N-1,-1,-1):
  right=i
  x=a[i]
  while len(s)>0 and x<s[-1][0]:
    right=s[-1][-1]
    s.pop()
  r.append(right)
  s.append([x,right])
r=r[::-1]
ans=0
for i,(x,le,ri) in enumerate(zip(a,l,r)):
  ans+=x*(i-le+1)*(ri-i+1)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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

b=[i for i in range(1,N+1)]

A=[]
for i in range(N):
    A.append([a[i],b[i]])
A.sort(reverse=True)

PL=[i for i in range(N+1)]+[N+1]
PR=[i for i in range(N+1)]+[N+1]

def findL(x):
    if x==PL[x]:
        return x
    else:
        return findL(PL[x])
        
def findR(x):
    if x==PR[x]:
        return x
    else:
        return findR(PR[x])

ans=0
for i in range(N):
    ans+=A[i][0]*(A[i][1]-findL(A[i][1]-1))*(findR(A[i][1]+1)-A[i][1])
    
    
    PL[A[i][1]]=findL(A[i][1]-1)
    PR[A[i][1]]=findR(A[i][1]+1)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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

b=[i for i in range(1,N+1)]

A=[]
for i in range(N):
    A.append([a[i],b[i]])
A.sort(reverse=True)

PL=[i for i in range(N+1)]+[N+1]
PR=[i for i in range(N+1)]+[N+1]

def findL(x):
    if x==PL[x]:
        return x
    else:
        return findL(PL[x])
        
def findR(x):
    if x==PR[x]:
        return x
    else:
        return findR(PR[x])

ans=0
for i in range(N):
    ans+=A[i][0]*(A[i][1]-findL(A[i][1]-1))*(findR(A[i][1]+1)-A[i][1])
    
    
    PL[A[i][1]]=findL(A[i][1]-1)
    PR[A[i][1]]=findR(A[i][1]+1)
print(ans)

Solution (Python):
import heapq

n = int(input())
alist = list(map(int, input().split()))

ad = {}
for i, a in enumerate(alist):
  ad[a] = i

h = []
right = [n-1] * n

for i in range(n):
  while h and -h[0] > alist[i]:
    v = -heapq.heappop(h)
    right[ad[v]] = i - 1
  heapq.heappush(h, -alist[i])

h = []
left = [0] * n

for i in reversed(range(n)):
  while h and -h[0] > alist[i]:
    v = -heapq.heappop(h)
    left[ad[v]] = i + 1
  heapq.heappush(h, -alist[i])

ans = 0
for i in range(n):
  ans += alist[i] * (i - left[i] + 1) * (right[i] - i + 1)

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
d = {}
for i,j in enumerate(a):
    d[j] = i

uf = [-1]*n
def root(a):
    if uf[a] < 0:
        return a
    uf[a] = root(uf[a])
    return uf[a]
def unite(a,b):
    ra,rb = root(a),root(b)
    if ra==rb:
        return False
    if uf[ra] > uf[rb]:
        ra,rb = rb,ra
    uf[ra] += uf[rb]
    uf[rb] = ra
    return True

ans = 0
for i in range(n,0,-1):
    left=right=0
    ind = d[i]

    if ind<n-1 and a[ind] < a[ind+1]:
        right -= uf[root(ind+1)]
        unite(ind, ind+1)
    if ind>0 and a[ind] < a[ind-1]:
        left -= uf[root(ind-1)]
        unite(ind, ind-1)
    ans += i*(left+1)*(right+1)

print(ans)

Solution (Python):
n=int(input())
s=list(map(int,input().split()))
p,q,r,d=[0]*(n+1),[i for i in range(n+2)],[i for i in range(n+2)],0
for i in range(n):
    p[s[i]]=i
for i in range(n,0,-1):
    h=p[i]
    x,y=q[h],r[h]
    d+=i*(h-x+1)*(y-h+1)
    q[y+1],r[x-1]=x,y
print(d)

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
b = [0] * (N + 1)
for i in range(N):
    b[a[i]] = i + 1
l = [i for i in range(N + 2)]
r = [i for i in range(N + 2)]
ans = 0
for i in range(N, 0, -1):
    m = b[i]
    x = l[m]
    y = r[m]
    ans += (m - x + 1) * (y - m + 1) * i
    r[x - 1] = y
    l[y + 1] = x
print(ans)

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
b = [0] * (N + 1)
for i in range(N):
    b[a[i]] = i + 1
l = [i for i in range(N + 2)]
r = [i for i in range(N + 2)]
ans = 0
for i in range(N, 0, -1):
    m = b[i]
    x = l[m]
    y = r[m]
    ans += (m - x + 1) * (y - m + 1) * i
    r[x - 1] = y
    l[y + 1] = x
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.size[y] += self.size[x]
            else:
                self.par[y] = x
                self.size[x] += self.size[y]

            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def tree_size(self, x):
        return self.size[self.find(x)]


N = int(input())
a = [-1] + [int(_) for _ in input().split()] + [-1]
uf = UnionFind(N+1)
place = [-1]*(N+1)
ans = 0

for i in range(1, N+1):
    place[a[i]] = i

for i in range(N, 0, -1):
    left = right = 0
    if a[place[i]] < a[place[i]-1]:
        left = uf.tree_size(uf.find(a[place[i]-1]))
        uf.unite(a[place[i]], a[place[i]-1])
    
    if a[place[i]] < a[place[i]+1]:
        right = uf.tree_size(uf.find(a[place[i]+1]))
        uf.unite(a[place[i]], a[place[i]+1])
    
    ans += (left+1)*(right+1)*a[place[i]]

print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    x = S()
    s = 0
    ans = len(x)
    for i in x:
        if i == "S":
            s += 1
        else:
            if s > 0:
                s -= 1
                ans -= 2
    print(ans)
    return


def B():
    n = I()
    a = LI()
    f = [0 for i in range(n+1)]
    for i in range(n):
        f[a[i]] = i
    l = [i for i in range(n+1)]
    r = [i for i in range(n+1)]
    ans = 0
    for i in range(1,n+1)[::-1]:
        j = f[i]
        ans += (j-l[j]+1)*(r[j]-j+1)*i
        l[r[j]+1] = l[j]
        r[l[j]-1] = r[j]
    print(ans)
    return


def C():
    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    B()

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

l = []
r = []
s = []

for i, x in enumerate(a):
    left = i
    while len(s) > 0  and x < s[-1][0]:
        left = s[-1][1]
        s.pop()
        
    l.append(left)    
    s.append([x, left])

s = []
for i in range(n-1, -1, -1):
    right = i
    x = a[i]
    while len(s) > 0  and x < s[-1][0]:
        right = s[-1][1]
        s.pop()
        
    r.append(right)    
    s.append([x, right])
r = r[::-1]

ans = 0    
for i, (x, left, right)  in enumerate(zip(a,l,r)):
    ans += x * (right+1-i) * (i+1-left)
print(ans)

Solution (Python):
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
    ll = list(range(N + 1))
    rr = list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        idx = idxs[a]
        l, r = ll[idx], rr[idx]
        ans += (idx - l + 1) * (r - idx + 1) * a
        ll[r + 1] = l
        rr[l - 1] = r

    return ans

print(main())

Solution (Python):
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
    ll = list(range(N + 1))
    rr = list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        idx = idxs[a]
        l, r = ll[idx], rr[idx]
        ans += (idx - l + 1) * (r - idx + 1) * a
        ll[r + 1] = l
        rr[l - 1] = r

    return ans

print(main())