CodeEff/ECCO huggingface dataset:
# Original solution
class BIT_index:
    def __init__(self, n):
        self.BIT_prev = [n] * (n + 1)
        self.BIT_next = [n] * (n + 1)
        self.n = n

    def __addElement(self, BIT, idx):
        value = idx
        idx += 1
        while idx > 0:
            BIT[idx] = min(BIT[idx], value)
            idx -= idx & -idx

    def addElement(self, idx):
        self.__addElement(self.BIT_prev, self.n - 1 - idx)
        self.__addElement(self.BIT_next, idx)

    def __getIndex(self, BIT, idx):
        idx += 1
        ans = self.n
        while idx <= self.n:
            ans = min(ans, BIT[idx])
            idx += idx & -idx
        return ans

    def getIndexPrev(self, idx):
        return self.__getIndex(self.BIT_prev, self.n - 1 - idx)

    def getIndexNext(self, idx):
        return self.__getIndex(self.BIT_next, idx)


N = int(eval(input()))
As = list(map(int, input().split()))

Bs = [i for A, i in sorted([(As[i], i) for i in range(N)])]

BIT = BIT_index(N)
ans = 0
for i, B in enumerate(Bs):
    iN = BIT.getIndexNext(B)
    iP = BIT.getIndexPrev(B)
    BIT.addElement(B)
    ans += (i + 1) * (iN - B) * (B - (N - 1 - iP))

print(ans)


# Optimized solution
N = int(eval(input()))
As = list(map(int, input().split()))

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

ans = 0
iLs = list(range(N + 1))
iRs = list(range(N + 1))
for A in reversed(list(range(1, N + 1))):
    iA = iAs[A]
    iL, iR = iLs[iA], iRs[iA]
    ans += A * (iA - iL + 1) * (iR - iA + 1)
    iLs[iR + 1] = iL
    iRs[iL - 1] = iR

print(ans)
# Original solution
N = int(eval(input()))
As = list(map(int, input().split()))

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

ans = 0
iLs = list(range(N + 1))
iRs = list(range(N + 1))
for A in reversed(list(range(1, N + 1))):
    iA = iAs[A]
    iL, iR = iLs[iA], iRs[iA]
    ans += A * (iA - iL + 1) * (iR - iA + 1)
    iLs[iR + 1] = iL
    iRs[iL - 1] = iR

print(ans)


# Optimized solution
def getNums(As):
    nums = [0] * N
    stack = [(-1, 0)]
    for iA, A in enumerate(As):
        while stack[-1][1] > A:
            stack.pop()
        nums[iA] = iA - stack[-1][0]
        stack.append((iA, A))

    return nums


N = int(eval(input()))
As = list(map(int, input().split()))

numLs = getNums(As)
numRs = getNums(reversed(As))
print((sum([A * numL * numR for A, numL, numR in zip(As, numLs, reversed(numRs))])))
# Original solution
import sys
from operator import itemgetter


class BinaryIndexedTreeCustom:
    def __init__(self, n, init, func):
        self.size = n
        self.tree = [init] * (n + 1)
        self.depth = n.bit_length()
        self.init = init
        self.func = func

    def get(self, i):
        s = self.init
        tr = self.tree
        f = self.func
        while i > 0:
            s = f(s, tr[i])
            i -= i & -i
        return s

    def put(self, i, x):
        n = self.size
        tr = self.tree
        f = self.func
        while i <= n:
            y = tr[i]
            tr[i] = f(tr[i], x)
            if y == tr[i]:
                break
            i += i & -i


n, *aaa = list(map(int, sys.stdin.buffer.read().split()))
bit1 = BinaryIndexedTreeCustom(n, 0, max)
bit2 = BinaryIndexedTreeCustom(n, n + 1, min)
aaa_with_index = list(enumerate(aaa, start=1))
aaa_with_index.sort(key=itemgetter(1))
ans = 0
for i, a in aaa_with_index:
    li = bit1.get(i)
    ri = bit2.get(n - i)
    ans += a * (i - li) * (ri - i)
    bit1.put(i, i)
    bit2.put(n + 1 - i, i)
print(ans)


# Optimized solution
import sys
from operator import itemgetter

n, *aaa = list(map(int, sys.stdin.buffer.read().split()))
aaa_with_index = list(enumerate(aaa, start=1))
aaa_with_index.sort(key=itemgetter(1), reverse=True)
left = list(range(-1, n + 1))
right = list(range(1, n + 3))
ans = 0
for i, a in aaa_with_index:
    li = left[i]
    ri = right[i]
    ans += a * (i - li) * (ri - i)
    left[ri] = li
    right[li] = ri

print(ans)
# Original solution
import bisect
def inpl(): return [int(i) for i in input().split()]
N = int(eval(input()))
a = inpl()
b = [0 for _ in range(N)]
for i in range(N):
    b[a[i]-1] = i+1
rng = [0, N+1]
ans = 0
for i, v in enumerate(b):
    x = bisect.bisect_left(rng, v)
    st = rng[x-1]
    en = rng[x]
    ans += (i+1)*(v-st)*(en-v)
    bisect.insort_left(rng, v)
print(ans)

# Optimized solution
def inpl(): return [int(i) for i in input().split()]
N = int(eval(input()))
a = inpl()
b = {a[i]: i for i in range(N)}

left = list(range(N+2))
right = list(range(N+2))

ans = 0
for i in range(N,0,-1):
    x = b[i]
    ans += i*(right[x]-x +1)*(x-left[x] +1)
    right[left[x] - 1] = right[x]
    left[right[x] + 1] = left[x]
print(ans)
# Original solution
n = int(eval(input()))
A = [[int(a),i] for i,a in enumerate(input().split())]
A.sort()
bit = [0]*(n+1)

def sum(i):
    # [0, i) の要素の総和を返す
    s = 0
    while i>0:
        s += bit[i]
        i -= i & -i
    return s
# 0 index を 1 index に変更  転倒数を求めるなら1を足していく
def add(i, x):
    i += 1
    while i <= n:
        bit[i] += x
        i += i & -i

# 総和がx以上になる位置のindex をbinary search
def bsearch(x):
    le = 0
    ri = 1<<(n.bit_length()-1)
    while ri > 0:
        if le+ri <= n and bit[le+ri]<x:
            x -= bit[le+ri]
            le += ri
        ri >>= 1
    return le+1 

ans = 0
for i in range(n):
    x,ind = A[i]
    s = sum(ind)
    if s == 0:
        l = 0
    else:
        l = bsearch(s)
    s2 = s+1
    if s2 > i:
        r = n
    else:
        r = bsearch(s2)-1
    ans += x*(r-ind)*(ind-l+1)
    add(ind,1)
print(ans)

# Optimized solution
n = int(eval(input()))
A = list(map(int,input().split()))
l = [i-1 for i in range(n+2)]
r = [i+1 for i in range(n+2)]
ind = [0]*n

for i,a in enumerate(A):
    ind[a-1] = i

ans = 0
for i in range(n-1,-1,-1):
    x = ind[i]
    ans += (i+1)*(r[x]-x)*(x-l[x])
    l[r[x]],r[l[x]], = l[x],r[x]
print(ans)
# Original solution
from bisect import bisect_left

N = int(eval(input()))
*A, = list(map(int, input().split()))
indices = {a: i for i, a in enumerate(A)}
seen_idx = [-1, N]
ans = 0
for a in range(1, N+1):
    idx = indices[a]
    t = bisect_left(seen_idx, idx)
    seen_idx = seen_idx[:t] + [idx] + seen_idx[t:]
    left = idx - seen_idx[t-1]
    right = seen_idx[t+1] - idx
    ans += left * right * a
print(ans)

# Optimized solution
N = int(eval(input()))
*A, = list(map(int, input().split()))
indices = {a: i for i, a in enumerate(A)}
left = {i: i for i in range(N)} # "left[i] = l" is equivalent to "A[l], ..., A[i-1] > A[i]"
right = {i: i for i in range(N)} # "right[i] = r" is equivalent to "A[i] < A[i+1], ..., A[r]"
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 # A[l-1] < A[l], ..., A[r] > A[r+1]
print(ans)
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
p=[None]*N
for i,a in enumerate(A):
    p[a-1]=i
ans=0
b={-1:1,N:1}
from bisect import bisect
for i in range(N):
    bs=sorted(b.keys())
    s=bisect(bs,p[i])
    ans+=(i+1)*(p[i]-bs[s-1])*(bs[s]-p[i])
    b[p[i]]=1
print(ans)

# Optimized solution
N=int(eval(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)
# Original solution
n=int(eval(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)

# Optimized solution
def main():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    a = sorted(list(enumerate(a)), key=lambda x: -x[1])

    class unionfind():
        # size:要素数,tree：unionfind木
        def __init__(self, size):  # self,要素数
            self.size = size
            self.tree = [i for i in range(self.size)]  # root,depth

        # rootを探す
        def root(self, index):
            temp_list = []
            temp = self.tree[index]
            while index != temp:
                temp_list.append(index)
                index = temp
                temp = self.tree[index]
            for i in temp_list:
                self.tree[i] = index
            return index

        # 結合
        def unite_r(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            if r1 < r2:
                self.tree[r1] = r2
            else:
                self.tree[r2] = r1

        def unite_l(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            if r1 > r2:
                self.tree[r1] = r2
            else:
                self.tree[r2] = r1

        # 同じか判定
        def same(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            return r1 == r2

    ur = unionfind(n+2)
    ul = unionfind(n+2)
    vis = [False]*(n+2)
    ans = 0
    for i, j in a:
        vis[i+1] = True
        if vis[i+2]:
            ur.unite_r(i+1, i+2)
            ul.unite_l(i+1, i+2)
        if vis[i]:
            ur.unite_r(i, i+1)
            ul.unite_l(i, i+1)
        ans += j*(ur.root(i+1)-i)*(i+2-ul.root(i+1))
    print(ans)


main()
# Original solution
def main():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    a = sorted(list(enumerate(a)), key=lambda x: -x[1])

    class unionfind():
        # size:要素数,tree：unionfind木
        def __init__(self, size):  # self,要素数
            self.size = size
            self.tree = [i for i in range(self.size)]  # root,depth

        # rootを探す
        def root(self, index):
            temp_list = []
            temp = self.tree[index]
            while index != temp:
                temp_list.append(index)
                index = temp
                temp = self.tree[index]
            for i in temp_list:
                self.tree[i] = index
            return index

        # 結合
        def unite_r(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            if r1 < r2:
                self.tree[r1] = r2
            else:
                self.tree[r2] = r1

        def unite_l(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            if r1 > r2:
                self.tree[r1] = r2
            else:
                self.tree[r2] = r1

        # 同じか判定
        def same(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            return r1 == r2

    ur = unionfind(n+2)
    ul = unionfind(n+2)
    vis = [False]*(n+2)
    ans = 0
    for i, j in a:
        vis[i+1] = True
        if vis[i+2]:
            ur.unite_r(i+1, i+2)
            ul.unite_l(i+1, i+2)
        if vis[i]:
            ur.unite_r(i, i+1)
            ul.unite_l(i, i+1)
        ans += j*(ur.root(i+1)-i)*(i+2-ul.root(i+1))
    print(ans)


main()


# Optimized solution
def main():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    a = sorted(list(enumerate(a)), key=lambda x: -x[1])
    L = [i for i in range(n+2)]  # 連結成分のうち一番左のindex
    R = [i for i in range(n+2)]  # 連結成分のうち一番右のindex
    ans = 0
    for i, j in a:  # 1-indexなので1ずれる
        M = R[i+1]  # 連結成分の最大値
        m = L[i+1]  # 連結成分の最小値
        ans += j*(M-i)*(i+2-m)  # 計算
        R[m-1] = M  # 連結成分の左端の更新
        L[M+1] = m  # 連結成分の右端の更新
    print(ans)


main()
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
p = [0]*(n+1)
ans = 0
for i in range(n):
  p[a[i]] = i+1
l = [i-1 for i in range(n+2)]
l[0] = 0
r = [i+1 for i in range(n+2)]
r[-1] = n+1
for i in range(n,0,-1):
  ans += (p[i]-l[p[i]])*(r[p[i]]-p[i])*i
  l[r[p[i]]] = l[p[i]]
  r[l[p[i]]] = r[p[i]]
print(ans)

# Optimized solution
N = int(eval(input()))
a = list(map(int, input().split()))

# indexをソート
b = [0] * N
for i in range(N):
    b[a[i] - 1] = i

# 初期化　端っこ対策としてひとつ余計に取っている
left = [0] * (N + 1)
right = [0] * (N + 1)
for i in range(N + 1):
    left[i] = i-1
    right[i] = i+1

# 更新
for idx in reversed(b):
    left[right[idx]] = left[idx]
    right[left[idx]] = right[idx]

ans = 0
for i in range(N):
    ans += a[i] * (i - left[i]) * (right[i] - i)

print(ans)
# Original solution
import bisect
N = int(eval(input()))
a = list(zip(list(map(int, input().split())), list(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)

# Optimized solution
N = int(eval(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)
# Original solution
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class SegmentTree():
   
    def __init__(self,N,f,unit):
        self.f = f
        self.unit = unit
        self.N = N
        self.tree = [self.unit] * (2*self.N)
        #self._build(array)
    
    def _build(self,array):
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def debug(self):
        print((self.tree))

def main():
    N = int(eval(input()))
    A = list(map(int,input().split()))

    st = SegmentTree(N,max,-1)
    L = [-1] * N
    for i,a in enumerate(A):
        L[i] = st.query(0,a - 1)
        st.update(a - 1,i)
    
    st = SegmentTree(N,min,N)
    R = [N] * N
    for i in range(N - 1,-1,-1):
        R[i] = st.query(0,A[i] - 1)
        st.update(A[i] - 1,i)
    
    ans = sum((R[i] - i)*(i - L[i])*A[i] for i in range(N))
    print(ans) 
if __name__ == '__main__':
    main()

# Optimized solution
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(eval(input()))
    A = list(enumerate(map(int,input().split())))
    A.sort(key = lambda x:-x[1])

    left = list(range(-1,N + 2))
    right = list(range(1,N + 4))
    ans = 0
    for i,a in A:
        L = left[i]
        R = right[i]
        ans += a*(i - L)*(R - i)
        left[R] = L
        right[L] = R
    print(ans)
if __name__ == '__main__':
    main()
# Original solution
import bisect
N=int(eval(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)

# Optimized solution
import sys
sys.setrecursionlimit(1000000)

N=int(eval(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)
#print(A)
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])
#print(PR)
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])
    #print(ans,A[i][1],(A[i][1]-findL(A[i][1])+1),findR(A[i][1])-A[i][1]+1)
    #print(PR)
    PL[A[i][1]]=findL(A[i][1]-1)
    PR[A[i][1]]=findR(A[i][1]+1)
print(ans)
# Original solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    b = [0]*n
    for _ in range(n):
        b[a[_]-1] = _
    r = (b[0]+1) * (n-b[0])
    c = [b[0]]
    m = 2
    for i in b[1:]:
        ri = bisect.bisect(c, i)
        if ri == 0:
            r += (i+1) * (c[ri]-i) * m
        elif ri == m-1:
            r += (i-c[ri-1]) * (n-i) * m
        else:
            r += (i-c[ri-1]) * (c[ri]-i) * m
        m += 1
        c = c[:ri] + [i] + c[ri:]

    return r

print((f()))


# Optimized solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    l = list(range(n+2))
    r = list(range(n+2))
    b = [0]*(n+2)
    for i, x in enumerate(a, 1):
        b[x] = i
    c = 0
    for i in range(n,0,-1):
        bi = b[i]
        c += i * (r[bi] - bi + 1) * (bi - l[bi] + 1)
        r[l[bi]-1] = r[bi]
        l[r[bi]+1] = l[bi]
    return c

print((f()))
# Original solution
def main():
  n=int(eval(input()))
  a=list(map(int,input().split()))
  def func(l,i):
    ret=l*(l+1)//2
    ret-=i*(i+1)//2
    ret-=(l-i-1)*(l-i)//2
    return ret
  dn={a[i]:i+1 for i in range(n)}
  from bisect import bisect_left,insort
  space=[0,n+1]
  ans=0
  for i in range(1,n+1):
    t=dn[i]
    tl=bisect_left(space,t)
    l=space[tl-1]
    r=space[tl]
    lg=r-l-1
    ans+=func(lg,t-l-1)*i
    insort(space,t)
  print(ans)
if __name__=='__main__':
  main()

# Optimized solution
n=int(eval(input()))
p=list(map(int,input().split()))
dn={x:i for i,x in enumerate(p)}

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc=segfunc, ide_ele=ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

st=SegTree([0]*n)
ans=0

for k in range(1,n+1):
    i=dn[k]
    # idx=iを含み、区間和が0になる最長の区間を調べる。
    l,r=0,i
    while r-l>1:
        x=(l+r)//2
        if st.query(x,i+1)>0:
            l,r=x,r
        else:
            l,r=l,x
    l0=l if st.query(l,i+1)==0 else r
    l,r=i,n-1
    while r-l>1:
        x=(l+r)//2
        if st.query(i,x+1)>0:
            l,r=l,x
        else:
            l,r=x,r
    r0=r if st.query(i,r+1)==0 else l
    ans+=k*(i-l0+1)*(r0-i+1)
    st.update(i,1)
print(ans)
# Original solution
#!/usr/bin/env python3
class UnionFind:
    __slots__ = ['id','sz']

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

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

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

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

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

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




# Optimized solution
#!/usr/bin/env python3
ans=0
n=int(eval(input()))
A=list(map(int,input().split()))
B=[0]*(n+1)
for i in range(n):
    B[A[i]]=i+1
LL=[int(i) for i in range(n+2)]
RR=[int(i) for i in range(n+2)]
for i in range(n,0,-1):
    l=LL[B[i]]
    r=RR[B[i]]
    ans+=(B[i]-l+1)*(r-B[i]+1)*i
    LL[r+1]=l
    RR[l-1]=r
print(ans)