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):
n = int(input())
A = list(map(int, input().split()))
A = [a-1 for a in A]

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

R = [n]*n
q = []
import heapq
heapq.heapify(q)
for i in range(n):
    while q:
        if -q[0] > A[i]:
            v = -heapq.heappop(q)
            R[v] = i
        else:
            break
    heapq.heappush(q, -A[i])

L = [-1]*n
q = []
heapq.heapify(q)
for i in reversed(range(n)):
    while q:
        if -q[0] > A[i]:
            v = -heapq.heappop(q)
            L[v] = i
        else:
            break
    heapq.heappush(q, -A[i])



ans = 0
for i in range(n):
    ans += (P[i]-L[i])*(R[i]-P[i])*(i+1)
print(ans)

Solution (Python):
code = r"""


from libcpp.set cimport set
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
from cython.operator cimport dereference as deref
from cython.operator cimport preincrement as preinc, predecrement as predec
from cython.operator cimport postincrement as postinc, postdecrement as postdec
cdef int cin() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: break
        c = c * 10 + b
    return c
cdef int n = cin(), i
cdef long c
cdef vector[long] a = vector[long](n)
for i in range(n): a[cin() - 1] = i
cdef set[long] s = set[long]([-1, n])
cdef set[long].iterator it
for i in range(n):
    it = s.lower_bound(a[i])
    c += (deref(postdec(it)) - a[i]) * (a[i] - deref(it)) * (i + 1)
    s.insert(a[i])
printf('%ld\n', c)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
code = r"""


from libcpp.set cimport set
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
from cython.operator cimport dereference as deref
from cython.operator cimport preincrement as preinc, predecrement as predec
from cython.operator cimport postincrement as postinc, postdecrement as postdec
cdef int cin() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: break
        c = c * 10 + b
    return c
cdef int n = cin(), i
cdef long c
cdef vector[long] a = vector[long](n)
for i in range(n): a[cin() - 1] = i
cdef set[long] s = set[long]([-1, n])
cdef set[long].iterator it
for i in range(n):
    it = s.lower_bound(a[i])
    c += (deref(postdec(it)) - a[i]) * (a[i] - deref(it)) * (i + 1)
    s.insert(a[i])
printf('%ld\n', c)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
code = r"""

from libcpp.set cimport set
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
from cython.operator cimport dereference as deref
from cython.operator cimport preincrement as preinc, predecrement as predec
from cython.operator cimport postincrement as postinc, postdecrement as postdec
cdef int cin() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: break
        c = c * 10 + b
    return c
cdef int n = cin(), i
cdef long c
cdef vector[long] a = vector[long](n)
for i in range(n): a[cin() - 1] = i
cdef set[long] s = set[long]([-1, n])
cdef set[long].iterator it
for i in range(n):
    it = s.lower_bound(a[i])
    c += (deref(postdec(it)) - a[i]) * (a[i] - deref(it)) * (i + 1)
    s.insert(a[i])
printf('%ld\n', c)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rg?P`QD5d7~`ER<5McXC316zM&QJxYwLw=|bXvi9iPcVn!*mIj3E%<Q-yxr3ep&rBvXV3ZwaHR4g1Wj1(s0YjahrYazVrpx3!gWP{{AE?>+jZWc@q6*xT+vpKlpOxRi<jL}obo!Ie&Q@+huWr41^f<_8HG&E$jG5S@_IN?d3D%kJaR4!tRGSxI-AJa%K+eW=JJ4{1!-8JVWDx2kiKi24txfXx@btV<Gzj|whXy*2>V3nbn}$cI4^Tq4z
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
code = r"""

from libcpp.set cimport set
from libcpp.vector cimport vector
from cython.operator cimport dereference as deref, predecrement as dec
cdef int n = int(input()), i
cdef long c
cdef vector[long] a = [*map(int, input().split())]
cdef vector[long] l = [0] * n
for i in range(n): l[a[i] - 1] = i
cdef set[long] s = set[long]([-1, n])
cdef set[long].iterator it
for i in range(n):
    it = s.lower_bound(l[i])
    c += (deref(it) - l[i]) * (l[i] - deref(dec(it))) * (i + 1)
    s.insert(l[i])
print(c)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
code = r"""

from libcpp.set cimport set
from libcpp.vector cimport vector
from libcpp.iterator cimport iterator
from cython.operator cimport dereference as deref, predecrement as dec
cdef int n = int(input()), i
cdef long c
cdef iterator it, jt
cdef vector[long] a = [*map(int, input().split())]
cdef vector[long] l = [0] * n
for i in range(n): l[a[i] - 1] = i
cdef set[long] s = set[long]([-1, n])
for i in range(n):
    c += (deref(s.lower_bound(l[i])) - l[i]) * (l[i] - deref(dec(s.lower_bound(l[i])))) * (i + 1)
    s.insert(l[i])
print(c)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
class segTreeMin:
  
  inf = 10**10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.inf = num
    s.T = [s.inf] * (2 * s.N)
  def do(s, l, r):
    
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i + 1, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, x):
    return s.T[x + s.N - 1]
  def getArea(s, l, r):
    L = l + s.N
    R = r + s.N
    p = s.inf
    while L < R:
      if R & 1:
        R -= 1
        p = s.do(p, s.T[R - 1])
      if L & 1:
        p = s.do(p, s.T[L - 1])
        L += 1
      L >>= 1
      R >>= 1
    return p

class segTreeMax:
  
  inf = -1
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N)
  def do(s, l, r):
    
    return max(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i + 1, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, x):
    return s.T[x + s.N - 1]
  def getArea(s, l, r):
    L = l + s.N
    R = r + s.N
    p = s.inf
    while L < R:
      if R & 1:
        R -= 1
        p = s.do(p, s.T[R - 1])
      if L & 1:
        p = s.do(p, s.T[L - 1])
        L += 1
      L >>= 1
      R >>= 1
    return p

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

segMax = segTreeMax(N)
segMin = segTreeMin(N)

D = [[0] * 2 for _ in range(N)]
L = [0] * N

for i in range(N):
  t = a[i] - 1
  L[t] = i
  
ans = 0
for i in range(N):
  l = segMax.getArea(0, L[i] + 1)
  r = segMin.getArea(L[i], N)
  ans += (i + 1) * (L[i] - l) * (r - L[i])
  segMax.update(L[i], L[i])
  segMin.update(L[i], L[i])

print(ans)

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

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

import heapq
q = []
heapq.heapify(q)
R = [n-1]*n
for i, a in enumerate(A):
    while q and q[0]*(-1) > a:
        v = heapq.heappop(q)*(-1)
        R[v-1] = i-1
    heapq.heappush(q, a*(-1))

q = []
L = [0]*n
for j in range(n):
    i = n-1-j
    a = A[i]
    while q and q[0]*(-1) > a:
        v = heapq.heappop(q)*(-1)
        L[v-1] = i+1
    heapq.heappush(q, a*(-1))



ans = 0
for i in range(n):
    a = i+1
    l, r, p = L[i], R[i], P[i]
    ans += (p-l+1)*(r-p+1)*a
print(ans)

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

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

import heapq
q = []
heapq.heapify(q)
R = [n-1]*n
for i, a in enumerate(A):
    while q and q[0]*(-1) > a:
        v = heapq.heappop(q)*(-1)
        R[v-1] = i-1
    heapq.heappush(q, a*(-1))

q = []
L = [0]*n
for j in range(n):
    i = n-1-j
    a = A[i]
    while q and q[0]*(-1) > a:
        v = heapq.heappop(q)*(-1)
        L[v-1] = i+1
    heapq.heappush(q, a*(-1))



ans = 0
for i in range(n):
    a = i+1
    l, r, p = L[i], R[i], P[i]
    ans += (p-l+1)*(r-p+1)*a
print(ans)

Solution (Python):
class Bit:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """
        (a0+a1+...+ai < x となる最大の i (存在しない時は -1 ) , その時の a0+a1+...+ai )
        a0+a1+...+ai <= x としたい場合は equal = True
        二分探索であるため、ai>=0 を満たす必要がある
        """
        sum_ = 0
        pos = -1    
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: 
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i+1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))



class BitImos:
    def __init__(self, n):
        self.n = n
        self.p = Bit(self.n + 1)
        self.q = Bit(self.n + 1)

    def add(self, s, t, x):
        """ 区間は閉区間 [s,t] で与えられる。原理は Imos法 と同じ。"""
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def sum(self, s, t):
        """ 半閉区間[s,t)の累積和を与える """
        return self.p.sum(t) + self.q.sum(t) * t - self.p.sum(s) - self.q.sum(s) * s

    def __getitem__(self, s):
        """ 区間加算後の s 番目の要素をO(log N)で取り出す。Imos法だとこの操作にO(N)かかる。"""
        return self.q.sum(s+1)      

    def __iter__(self):
        """ max(self) で普段 Imos法 でやってることが出来る。"""
        for t in range(self.n):
            yield self.q.sum(t+1)

    def __str__(self):
        text1 = " ".join(["element: "] + list(map(str, self)))
        return text1



class BitSet:

    """ 挿入、削除、k番目の値を取得、全てがO(logN)で可能。重複にも対応。"""
    """ 原理的に ai>=0 であるため、二分探索が可能である点も重要　　　　　"""
    def __init__(self, n, A=[]):
        """
        :param n: Aの要素の最大値
        :param A:
        self.size: BitSetに含まれている要素の個数
        """
        self.n = n
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(x, 1)
        self.size += 1
        self.flip += self.size - self.p.sum(x+1)        

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def order(self,x):
        """
        x が小さい順で何番目かを取得（1-indexed)
        BIT.order(x) = bisect_left(BIT.sort(),x) + 1
        BIT.minimum(BIT.order(x)) = BIT.lower_bound(x) = Aに含まれる x 以上の最小の要素
        """
        return self.p.sum(x) + 1

    def bisect_left(self,x):
        if x <= self.n:
            return self.p.sum(x)
        else:
            return self.size

    def bisect_right(self,x):
        x += 1
        if x <= self.n:
            return self.p.sum(x)
        else:
            return self.size

    def flip_counter(self):
        return self.flip

    def count(self,x):
        return self.p[x]

    def minimum(self,k=1):
        """ k 番目に小さい値を取得 （1-indexed）  """
        if k <= self.size:
            return self.p.lower_bound(k)[0] + 1
        else:
            sys.stderr.write("minimum: list index out of range (k={0})\n".format(k))

    def min(self):
        return self.minimum(1)

    def max(self):
        return self.p.lower_bound(self.size)[0] + 1

    def upper_bound(self,x):
        """ x以下の最大の要素の値を返す """
        k = self.p.sum(x+1)
        if k:
            return self.minimum(k)
        else:
            sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x))

    def lower_bound(self,x):
        """ x以上の最小の要素の値を返す """
        k = self.p.sum(x) + 1
        if k <= self.size:
            return self.minimum(k)
        else:
            sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x))

    def __getitem__(self, k):
        """ ソートした時の k 番目の要素 (0-indexed)  """
        if k >= 0:
            return self.minimum(k+1)
        else:
            return self.minimum(self.size + 1 + k)

    def __len__(self):
        return self.size

    def __iter__(self):
        for i in range(self.n+1):
            if self.p[i]:
                for _ in range(self.p[i]):
                    yield i

    def __str__(self):
        text1 = " ".join(list(map(str, self)))
        return "[" + text1 + "]"




import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
c = dict()
for i, a in enumerate(A,start=1):
    c[a] = i
B = BitSet(N+2)
B.add(0)
B.add(N+1)
res = 0
for a in sorted(A):
    s = c[a]
    b = B.bisect_left(s)
    if b==0:
        res += a*(B[b]-s)
    elif b==len(B):
        res += a*(s-B[b-1])
    else:
        res += a*(s-B[b-1])*(B[b]-s)
    B.add(s)
print(res)

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

left_amin = [0]*N

stack = [(0,-1)]

for i,a in enumerate(A):
    while stack[-1][0] > a:
        stack.pop()
    left_amin[i] = stack[-1][1]
    stack.append((a,i))

right_amin = [0]*N

stack = [(0,N)]

for i,a in zip(reversed(range(N)),reversed(A)):
    while stack[-1][0] > a:
        stack.pop()
    right_amin[i] = stack[-1][1]
    stack.append((a,i))


res = 0

for i,(l,r,a) in enumerate(zip(left_amin,right_amin,A)):
    res += a*(i-l)*(r-i)
print(res)

Solution (Python):
n = int(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)

Solution (Python):
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri <= self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

n = int(input())
a = [[int(x),i] for i,x in enumerate(input().split())]
a.sort()
bit = BIT(n)

ans = 0

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

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

left = [0] * (N + 1)
right = [0] * (N + 1)


buf = list()
for i in range(N):
    while len(buf) > 0 and a[buf[-1]] > a[i]:
        buf.pop()
    if len(buf) > 0:
        left[i] = buf[-1]
    else:
        left[i] = -1
    buf.append(i)


buf = list()
for i in reversed(range(N)):
    while len(buf) > 0 and a[buf[-1]] > a[i]:
        buf.pop()
    if len(buf) > 0:
        right[i] = buf[-1]
    else:
        right[i] = N
    buf.append(i)

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

print(ans)

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


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)

Solution (Python):
n=int(input())
p=list(map(int,input().split()))
dn={x:i for i,x in enumerate(p)}


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



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]
    
    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)

Solution (Python):
class Node:
    def __init__(self, key):
        self.key = key
        self.lch = None
        self.rch = None
        self.bias = 0


class AVLTree:
    def __init__(self):
        self.root = None

    def rotate_left(self, v):
        u = v.rch
        v.rch = u.lch
        u.lch = v
        if u.bias == -1:
            u.bias = v.bias = 0
        else:
            u.bias = 1
            v.bias = -1
        return u

    def rotate_right(self, v):
        u = v.lch
        v.lch = u.rch
        u.rch = v
        if u.bias == 1:
            u.bias = v.bias = 0
        else:
            u.bias = -1
            v.bias = 1
        return u

    def rotateLR(self, v):
        u = v.lch
        t = u.rch
        u.rch = t.lch
        t.lch = u
        v.lch = t.rch
        t.rch = v
        self.update_bias_double(t)
        return t

    def rotateRL(self, v):
        u = v.rch
        t = u.lch
        u.lch = t.rch
        t.rch = u
        v.rch = t.lch
        t.lch = v
        self.update_bias_double(t)
        return t

    def update_bias_double(self, v):
        if v.bias == 1:
            v.rch.bias = -1
            v.lch.bias = 0
        elif v.bias == -1:
            v.rch.bias = 0
            v.lch.bias = 1
        else:
            v.rch.bias = 0
            v.lch.bias = 0
        v.bias = 0

    def add(self, key):
        if self.root is None:
            self.root = Node(key)
            return

        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lch
            elif v.key < key:
                history.append((v, -1))
                v = v.rch
            else:
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lch = Node(key)
        else:
            p.rch = Node(key)

        while history:
            v, direction = history.pop()
            v.bias += direction

            new_v = None
            b = v.bias
            if b == 0:
                break

            if b == 2:
                u = v.lch
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)
                break
            if b == -2:
                u = v.rch
                if u.bias == 1:
                    new_v = self.rotateRL(v)
                else:
                    new_v = self.rotate_left(v)
                break

        if new_v is not None:
            if len(history) == 0:
                self.root = new_v
                return
            p, pdir = history.pop()
            if pdir == 1:
                p.lch = new_v
            else:
                p.rch = new_v

    def lower_bound(self, key):
        ret = 1<<30
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret > v.key:
                    ret = v.key
                v = v.lch
            else:
                v = v.rch
        return ret

    def upper_bound(self, key):
        ret = -1
        v = self.root
        while v is not None:
            if v.key <= key:
                if ret < v.key:
                    ret = v.key
                v = v.rch
            else:
                v = v.lch
        return ret

if __name__ == '__main__':
    N = int(input())
    A = [(a, i) for i, a in enumerate(map(int, input().split()))]
    A.sort(reverse=True)

    T = AVLTree()
    T.add(-1)
    T.add(N)

    ans = 0
    while A:
        a, i = A.pop()
        l = T.upper_bound(i)
        r = T.lower_bound(i)
        ans += a*(r-i)*(i-l)
        T.add(i)
    print(ans)

Solution (Python):
class Node:
    def __init__(self, key):
        self.key = key
        self.lch = None
        self.rch = None
        self.bias = 0
        self.size = 1


class AVLTree:
    def __init__(self):
        self.root = None

    def rotate_left(self, v):
        u = v.rch

        u.size = v.size
        v.size -= u.rch.size + 1 if u.rch is not None else 1

        v.rch = u.lch
        u.lch = v
        if u.bias == -1:
            u.bias = v.bias = 0
        else:
            u.bias = 1
            v.bias = -1
        return u

    def rotate_right(self, v):
        u = v.lch

        u.size = v.size
        v.size -= u.lch.size + 1 if u.lch is not None else 1

        v.lch = u.rch
        u.rch = v
        if u.bias == 1:
            u.bias = v.bias = 0
        else:
            u.bias = -1
            v.bias = 1
        return u

    def rotateLR(self, v):
        u = v.lch
        t = u.rch

        t.size = v.size
        v.size -= u.size - (t.rch.size if t.rch is not None else 0)
        u.size -= t.rch.size + 1 if t.rch is not None else 1

        u.rch = t.lch
        t.lch = u
        v.lch = t.rch
        t.rch = v
        self.update_bias_double(t)
        return t

    def rotateRL(self, v):
        u = v.rch
        t = u.lch

        t.size = v.size
        v.size -= u.size - (t.lch.size if t.lch is not None else 0)
        u.size -= t.lch.size + 1 if t.lch is not None else 1

        u.lch = t.rch
        t.rch = u
        v.rch = t.lch
        t.lch = v
        self.update_bias_double(t)
        return t

    def update_bias_double(self, v):
        if v.bias == 1:
            v.rch.bias = -1
            v.lch.bias = 0
        elif v.bias == -1:
            v.rch.bias = 0
            v.lch.bias = 1
        else:
            v.rch.bias = 0
            v.lch.bias = 0
        v.bias = 0

    def add(self, key):
        if self.root is None:
            self.root = Node(key)
            return

        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lch
            elif v.key < key:
                history.append((v, -1))
                v = v.rch
            else:
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lch = Node(key)
        else:
            p.rch = Node(key)

        while history:
            v, direction = history.pop()
            v.bias += direction
            v.size += 1

            new_v = None
            b = v.bias
            if b == 0:
                break

            if b == 2:
                u = v.lch
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)
                break
            if b == -2:
                u = v.rch
                if u.bias == 1:
                    new_v = self.rotateRL(v)
                else:
                    new_v = self.rotate_left(v)
                break

        if new_v is not None:
            if len(history) == 0:
                self.root = new_v
                return
            p, pdir = history.pop()
            p.size += 1
            if pdir == 1:
                p.lch = new_v
            else:
                p.rch = new_v

        while history:
            p, pdir = history.pop()
            p.size += 1

    def remove(self, key):
        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lch
            elif v.key < key:
                history.append((v, -1))
                v = v.rch
            else:
                break
        else:
            return False

        if v.lch is not None:
            history.append((v, 1))
            lmax = v.lch
            while lmax.rch is not None:
                history.append((lmax, -1))
                lmax = lmax.rch

            v.key = lmax.key

            v = lmax

        c = v.rch if v.lch is None else v.lch

        if history:
            p, pdir = history[-1]
            if pdir == 1:
                p.lch = c
            else:
                p.rch = c
        else:
            self.root = c
            return True

        while history:
            new_p = None

            p, pdir = history.pop()
            p.bias -= pdir
            p.size -= 1

            b = p.bias
            if b == 2:
                if p.lch.bias == -1:
                    new_p = self.rotateLR(p)
                else:
                    new_p = self.rotate_right(p)

            elif b == -2:
                if p.rch.bias == 1:
                    new_p = self.rotateRL(p)
                else:
                    new_p = self.rotate_left(p)

            elif b != 0:
                break

            if new_p is not None:
                if len(history) == 0:
                    self.root = new_p
                    return True
                gp, gpdir = history[-1]
                if gpdir == 1:
                    gp.lch = new_p
                else:
                    gp.rch = new_p
                if new_p.bias != 0:
                    break

        while history:
            p, pdir = history.pop()
            p.size -= 1

        return True

    def member(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lch
            elif v.key < key:
                v = v.rch
            else:
                return True
        return False

    def lower_bound(self, key):
        ret = None
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret is None or ret > v.key:
                    ret = v.key
                v = v.lch
            else:
                v = v.rch
        return ret

    def upper_bound(self, key):
        ret = None
        v = self.root
        while v is not None:
            if v.key <= key:
                if ret is None or ret < v.key:
                    ret = v.key
                v = v.rch
            else:
                v = v.lch
        return ret

    def find_kth_element(self, k):
        v = self.root
        s = 0
        while v is not None:
            t = s+v.lch.size if v.lch is not None else s
            if t == k:
                return v.key
            elif t < k:
                s = t+1
                v = v.rch
            else:
                v = v.lch
        return None

    def __contains__(self, key): return self.member(key)
    def __delitem__(self, key): return self.remove(key)
    def __bool__(self): return self.root is not None
    def __len__(self): return self.root.size if self.root is not None else 0


if __name__ == '__main__':
    N = int(input())
    A = [(a, i) for i, a in enumerate(map(int, input().split()))]
    A.sort(reverse=True)

    T = AVLTree()
    T.add(-1)
    T.add(N)

    ans = 0
    while A:
        a, i = A.pop()
        l = T.upper_bound(i)
        r = T.lower_bound(i)
        ans += a*(r-i)*(i-l)
        T.add(i)
    print(ans)