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: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1)

    def search(self, k):
        if k > self.total:
            return -1
        if k == 0:
            return 0
        step = 1 << (self.size.bit_length() - 1)
        now_index = 0
        ret = 0
        while step:
            if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
                ret += self.bit[now_index + step - 1]
                now_index += step
            step >>= 1
        # now_indexを伸ばしいって、sumがk以上に達する直前まで伸ばし続けるならreturnのところでnow_index - 1。
        # その場合、bit.sum(now_index - 1) <= k < bit.sum(now_index)
        # 達してすぐのindexであれば-1しない
        return now_index

n = I()
A = LI()
val_idx = {A[j]:j+1 for j in range(n)}
bit = BIT(n + 2)
bit.add(n + 1, 1)
bit.add(0, 1)
ans = 0
for k in range(1, n + 1):
    idx = val_idx[k]
    bit.add(idx, 1)
    m = bit.sum(idx)
    r = bit.search(m + 1)
    l = bit.search(m - 1)
    ans += (r - idx) * (idx - l) * k

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

def while_pop(arr):
    res = [0] * N
    tmp = []
    for i, a in enumerate(arr):
        cnt = 1
        while tmp:
            aa, c = tmp.pop()
            if aa < a:
                tmp.append((aa, c))
                break
            else:
                cnt += c
        tmp.append((a, cnt))
        res[i] = cnt
    return res

left = while_pop(A)
right = while_pop(A[::-1])[::-1]

answer = 0
for i in range(N):
    answer += left[i] * right[i] * A[i]
    
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

left = [0] * N
tmp = []
for i, a in enumerate(A):
    cnt = 1
    while tmp:
        aa, c = tmp.pop()
        if aa < a:
            tmp.append((aa, c))
            break
        else:
            cnt += c
    tmp.append((a, cnt))
    left[i] = cnt
A =A [::-1]
right = [0] * N
tmp = []
for i, a in enumerate(A):
    cnt = 1
    while tmp:
        aa, c = tmp.pop()
        if aa < a:
            tmp.append((aa, c))
            break
        else:
            cnt += c
    tmp.append((a, cnt))
    right[i] = cnt
right = right[::-1]

A = A[::-1]
answer = 0
for i in range(N):
    answer += left[i] * right[i] * A[i]
    
print(answer)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
A = np.array(input().split(), dtype=np.int64)
left = np.zeros(n, dtype=np.int64)
right = np.zeros(n, dtype=np.int64)
stack = []
for i in range(n):
  now = 1
  while stack and stack[-1][0] > A[i]:
    num, dis = stack.pop()
    now += dis
  left[i] = now
  stack.append((A[i], left[i]))
stack = []
for i in range(n-1, -1, -1):
  now = 1
  while stack and stack[-1][0] > A[i]:
    num, dis = stack.pop()
    now += dis
  right[i] = now
  stack.append((A[i], right[i]))
mul = A*left*right
print(mul.sum())

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
def min_len(A):
    N = len(A)
    p = [-1]
    m = [0]
    L = []
    for i in range(N):
        a = A[i]
        while a < m[-1]:
            m.pop()
            p.pop()
        m.append(A[i])
        p.append(i)
        L.append(i-p[-2])
    return L

N = int(input())
A = inpl()
L = min_len(A)
R = min_len(A[::-1])
ans = sum(L[i]*R[N-1-i]*A[i] for i in range(N))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
すべてのiに対して
「a_iが最小値となる区間はいくつあるか?」を考える.
a_iより左側でa_iより小さいもののうち最もa_iに近いものをa_l
a_iより右側でa_iより小さいもののうち最もa_iに近いものをa_rとする.
最小値がa_iとなる区間は左側がl+1,l+2,...,i
                    　右側がi,i+1,...,r-1となる区間
⇒(i-l+1)x(r-i+1)個の区間でa_iが最小値をとる
すべてのiに対してこの個数を求める.
"""

n = I()
a = LI()
lst = [0]*(n+1)

for i in range(n):
    lst[a[i]] = i

l = [0]*n #各iに対して,a_iより左側でa_iより小さいもののうち最もa_iに近いもののindex
r = [0]*n #各iに対して,a_iより右側でa_iより小さいもののうち最もa_iに近いもののindex
ans = 0

#大きい値から見ていく
for x in range(1,n+1)[::-1]:
    #調べている数 := x
    #xの位置 := i
    i = lst[x]

    #iが右端でないかつ,iの右隣が自分(x)より大きい場合
    if i+1 < n and a[i+1] > x:
        #r[i+1] := iより右側でxより小さいもののうち最もiに近いもののindex
        #  ⇒ i <= j < r[i+1] に関してa[j]はx以上である.
        R = r[i+1]
    else:
        #右隣がいないまたは右隣が自分(x)より小さい場合
        R = i
    
    #iが左端でないかつ,iの左隣が自分(x)より大きい場合
    if i-1 >= 0 and a[i-1] > x:
        #l[i-1] := iより左側でxより小さいもののうち最もiに近いもののindex
        #  ⇒ l[i-1] < j <= i に関してa[j]はx以上である.
        L = l[i-1]
    else:
        #左隣がいないまたは左隣が自分(x)より小さい場合
        L = i
    
    # L < j < Rに関してa[j]はx以上であることが分かっている.
    # ⇒Rの位置から見て左側の区間はLまで
    # ⇒Lの位置から見て右側の区間はRまで
    l[R] = L
    r[L] = R
    ans += (i-L+1)*(R-i+1)*x
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・大きい数から挿入していく
・連結成分の両端を管理する
"""

N,*A = map(int,read().split())

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

left = list(range(1,len(A)+1))
right = list(range(-1,len(A)-1))
answer = 0
for i in ind[:0:-1]:
    # i番目に数を挿入
    l = left[i-1]; r = right[i+1]
    left[r] = l; right[l] = r
    x = i - l + 1; y = r - i + 1
    answer += A[i] * (x * y)

print(answer)

Submission status: Accepted

Solution code:
def main():
    n = int(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()

Submission status: Accepted

Solution code:
def main():
    n = int(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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

l = [N - 1 - i for i in range(N)]

st = deque([])

for i in range(N):


    while len(st) > 0 and st[-1][0] > a[i]:

        p = st.pop()
        l[p[1]] = i - p[1] - 1

    st.append([a[i],i])


a.reverse()
r = [N - 1 - i for i in range(N)]

st = deque([])

for i in range(N):


    while len(st) > 0 and st[-1][0] > a[i]:

        p = st.pop()
        r[p[1]] = i - p[1] - 1

    st.append([a[i],i])

r.reverse()
a.reverse()


ans = 0

for i in range(N):

    ans += (1 + (l[i]+r[i]) + (l[i] * r[i])) * a[i]

print (ans)

Submission status: Accepted

Solution code:
def main():
    N = int(raw_input())
    A = list(map(int, raw_input().split()))


    class RangeMinimumQuery:
        def __init__(self, n, inf=2 ** 31 - 1):
            self.n = 1 << (n - 1).bit_length()
            self.INF = inf
            self.segtree = [self.INF] * (2 * self.n)

        # i番目の値(0-indexed)をxに変更
        def update(self, i, x):
            i += self.n
            self.segtree[i] = x
            while i > 0:
                i //= 2
                self.segtree[i] = min(self.segtree[2 * i], self.segtree[2 * i + 1])

        # [l, r)のmin
        def query(self, l, r):
            L, R = l + self.n, r + self.n
            R = min(R, len(self.segtree))
            s = self.INF
            while L < R:
                if L & 1:
                    s = min(s, self.segtree[L])
                    L += 1

                if R & 1:
                    s = min(s, self.segtree[R - 1])
                    R -= 1

                L >>= 1
                R >>= 1

            return s


    # 番兵を設置
    A = [0] + A + [0]
    N = N + 2


    # セグ木を初期化
    RMQ = RangeMinimumQuery(N)
    for i, a in enumerate(A):
        RMQ.update(i, a)


    # r_indexes := 自分より右側であって、最も近い、自分より小さなもののindex
    # l_indexes := 自分より左側であって、最も近い、自分より小さなもののindex
    r_indexes = [None] * N
    l_indexes = [None] * N


    # 右側についてにぶたん := iからm内の区間最小値がai以上か？
    for i, a in enumerate(A[1: -1], start=1):
        ok, ng = i, N - 1
        while abs(ok - ng) > 1:
            m = (ok + ng) // 2

            if a <= RMQ.query(i, m + 1):
                ok = m
            else:
                ng = m

        r_indexes[i] = ok + 1

    # 左側についてにぶたん := iからm内の区間最小値がai以上か？
    for i, a in enumerate(A[1: -1], start=1):
        ok, ng = i, 0
        while abs(ok - ng) > 1:
            m = (ok + ng) // 2

            if a <= RMQ.query(m, i + 1):
                ok = m
            else:
                ng = m

        l_indexes[i] = ok - 1


    # 答えを計算
    ans = 0
    for i, (a, l, r) in enumerate(zip(A[1: -1], l_indexes[1: -1], r_indexes[1: -1]), start=1):
        ans += a * (i - l) * (r - i)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
	n, *a = map(int, open(0).read().split())
	idc = [0] * (n + 1)
	R = list(range(n + 2))
	L = R[:]
	ans = 0
	for i in range(n):
		idc[a[i]] = i + 1
	for x in range(n, 0, -1):
		i = idc[x]
		M = R[i]
		m = L[i]
		ans += x * (M - i + 1) * (i - m + 1)
		# とくに変更済みのとき連結
		R[m - 1] = M
		L[M + 1] = m
	print(ans)

if __name__=="__main__":
	main()

Submission status: Accepted

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

Submission status: Accepted

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

idx = {A[i]: i for i in range(N)}
 
ans = 0
idx_l, idx_r = list(range(N + 2)), list(range(N + 2))
for a in range(N, 0, -1):
    i = idx[a]
    l, r = idx_l[i], idx_r[i]
    ans += a * (i - l + 1) * (r - i + 1)
    idx_l[r + 1], idx_r[l - 1] = l, r
    
print(ans)

Submission status: Accepted

Solution code:
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#各数字がAのどこに入っているかをリストbにメモ
  
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)

Submission status: Accepted

Solution code:
N = int(input())
p = [None]+[int(c) for c in input().split()]
p_to_i = [None]*(N+1)
for i, x in enumerate(p[1:],1):
  p_to_i[x] = i

tree = [0]*(N+1)

def BIT_add(i):
  while i<=N:
    tree[i] += 1
    i += i&(-i)
    
def BIT_sum(i):
  s = 0
  while 0<i:
    s += tree[i]
    i -= i&(-i)
  return s

def BIT_search(c):
  s = 0
  step = 1<<(N.bit_length()-1)
  i = 0
  while step:
    if i+step<=N and s+tree[i+step]<c:
      i += step
      s += tree[i]
    step >>= 1
  return i+1

ans = 0
for i in range(1,N+1):
  c = p_to_i[i]
  L = BIT_sum(c)
  R = i-1-L
  BIT_add(c)
  a = BIT_search(L) if L>0 else 0
  b = BIT_search(L+2) if R>0 else N+1
  m = (c-a)*(b-c)
  ans += m*i
#  print(i, ans, a, b, c, L, R)
print(ans)

Submission status: Accepted

Solution code:
class Avltree:

  def __init__(self, key=None):
    self.key=key
    self.left=None
    self.right=None
    self.balance="Even"

  def search(self,key):
    node=self
    while node is not None:
      if node.key==key:
        return node
      if node.key>key:
        node=node.left
      elif node.key < key:
        node=node.right
    return None

  def search_lower(self, key, key_lower):
    node=self
    if node.key is None:
      return key_lower
    ans=key_lower
    while node is not None:
      if node.key<key:
        if ans<node.key:
          ans=node.key
        node=node.right
      elif node.key>=key:
        node=node.left
    return ans

  def search_higher(self, key, key_higher):
    node=self
    if node.key is None:
      return key_higher
    ans=key_higher
    while node is not None:
      if node.key>key:
        if ans>node.key:
          ans=node.key
        node=node.left
      elif node.key<=key:
        node=node.right
    return ans

  def end_lower(self, end_lower_key):
    node=self
    while node.left is not None:
      node=node.left
    return node.key

  def end_higher(self, end_higher_key):
    node=self
    while node.right is not None:
      node=node.right
    return node.key

  def DoubleRightRotation(self):
    tl=self.left
    self.left=tl.right.right
    tl.right.right=self
    tlr=tl.right
    tl.right=tlr.left
    tlr.left=tl
    if tlr.balance=="Left":
      tlr.right.balance="Right"
      tlr.left.balance="Even"
    elif tlr.balance=="Right":
      tlr.right.balance="Even"
      tlr.left.balance="Left"
    elif tlr.balance=="Even":
      tlr.right.balance="Even"
      tlr.left.balance="Even"
    tlr.balance="Even"
    return tlr

  def DoubleLeftRotation(self):
    tr=self.right
    self.right=tr.left.left
    tr.left.left=self
    trl=tr.left
    tr.left=trl.right
    trl.right=tr
    if trl.balance=="Right":
      trl.left.balance="Left"
      trl.right.balance="Even"
    elif trl.balance=="Left":
      trl.left.balance="Even"
      trl.right.balance="Right"
    elif trl.balance=="Even":
      trl.left.balance="Even"
      trl.right.balance="Even"
    trl.balance="Even"
    return trl

  def SingleLeftRotation(self):
    tr=self.right
    tr.balance="Even"
    self.balance="Even"
    self.right=tr.left
    tr.left=self
    return tr

  def SingleRightRotation(self):
    tl=self.left
    tl.balance="Even"
    self.balance="Even"
    self.left=tl.right
    tl.right=self
    return tl

  def replace(self, p, v):
    if p.left==self:
      p.left=v
    else:
      p.right=v

  def insert(self, key):
    if self.key is None:
      self.key=key
      return self
    if key<self.key:
      if self.left is None:
        self.left=Avltree(key)
      else:
        self.left.insertx(self, key)
    elif key>self.key:
      if self.right is None:
        self.right=Avltree(key)
      else:
        self.right.insertx(self, key)
    else:
      pass

  def insertx(self, p, key):
    node=self
    s=[]
    while True:
      if node.key>key:
        s.append((node, -1))
        if node.left is None:
          node.left=Avltree(key)
          node=node.left
          break
        else:
          node=node.left
      elif node.key<key:
        s.append((node, 1))
        if node.right is None:
          node.right=Avltree(key)
          node=node.right
          break
        else:
          node=node.right
    while len(s)!=0:
      node,direct=s.pop()
      if len(s)!=0:
        par=s[-1][0]
      else:
        par=p
      if direct==-1:
        if node.balance=="Right":
          node.balance="Even"
          break
        elif node.balance=="Even":
          node.balance="Left"
        elif node.balance=="Left":
          if node.left.balance=="Right":
            node.replace(par,node.DoubleRightRotation())
          elif node.left.balance=="Left":
            node.replace(par,node.SingleRightRotation())
          break
      elif direct==1:
        if node.balance=="Left":
          node.balance="Even"
          break
        elif node.balance=="Even":
          node.balance="Right"
        elif node.balance=="Right":
          if node.right.balance=="Left":
            node.replace(par,node.DoubleLeftRotation())
          elif node.right.balance=="Right":
            node.replace(par,node.SingleLeftRotation())
          break

  def to_s(self):
    return self.key

  def left_s(self):
    if self.left is None:
      return None
    return (self.left).key

  def right_s(self):
    if self.right is None:
      return None
    return (self.right).key

n=int(input())
a=list(map(int,input().split()))
ans=0
l=[0]*n
for i in range(n):
  l[a[i]-1]=i
root=Avltree()
for i in range(n):
  root.insert(l[i])
  ans+=(i+1)*(l[i]-root.search_lower(l[i],-1))*(root.search_higher(l[i],n)-l[i])
print(ans)

Submission status: Accepted

Solution code:
class Avltree:

  def __init__(self, key=None):
    self.key = key
    self.left = None
    self.right = None
    self.balance = "Even"

  def search(self, key):
    node = self
    while node is not None:
      if node.key == key:
        return node
      if node.key > key:
        node = node.left
      elif node.key < key:
        node = node.right
    return None

  def search_lower(self, key, key_lower):
    node = self
    if node.key is None:
      return key_lower
    ans = key_lower
    while node is not None:
      if node.key < key:
          if ans < node.key:
            ans = node.key
          node = node.right
      elif node.key >= key:
        node = node.left
    return ans

  def search_higher(self, key, key_higher):
    node = self
    if node.key is None:
      return key_higher
    ans = key_higher
    while node is not None:
      if node.key > key:
        if ans > node.key:
          ans = node.key
        node = node.left
      elif node.key <= key:
        node = node.right
    return ans

  def end_lower(self, end_lower_key):
    node = self
    while node.left is not None:
      node = node.left
    return node.key

  def end_higher(self, end_higher_key):
    node = self
    while node.right is not None:
      node = node.right
    return node.key

  def DoubleRightRotation(self):
    tl = self.left
    self.left = tl.right.right
    tl.right.right = self
    tlr = tl.right
    tl.right = tlr.left
    tlr.left = tl
    if tlr.balance == "Left":
      tlr.right.balance = "Right"
      tlr.left.balance = "Even"
    elif tlr.balance == "Right":
      tlr.right.balance = "Even"
      tlr.left.balance = "Left"
    elif tlr.balance == "Even":
      tlr.right.balance = "Even"
      tlr.left.balance = "Even"
    tlr.balance = "Even"
    return tlr

  def DoubleLeftRotation(self):
    tr = self.right
    self.right = tr.left.left
    tr.left.left = self
    trl = tr.left
    tr.left = trl.right
    trl.right = tr
    if trl.balance == "Right":
      trl.left.balance = "Left"
      trl.right.balance = "Even"
    elif trl.balance == "Left":
      trl.left.balance = "Even"
      trl.right.balance = "Right"
    elif trl.balance == "Even":
      trl.left.balance = "Even"
      trl.right.balance = "Even"
    trl.balance = "Even"
    return trl

  def SingleLeftRotation(self):
    tr = self.right
    tr.balance = "Even"
    self.balance = "Even"
    self.right = tr.left
    tr.left = self
    return tr

  def SingleRightRotation(self):
    tl = self.left
    tl.balance = "Even"
    self.balance = "Even"
    self.left = tl.right
    tl.right = self
    return tl

  def replace(self, p, v):
    if p.left == self:
      p.left = v
    else:
      p.right = v

  def insert(self, key):
    if self.key is None:
      self.key = key
      return self
    if key < self.key:
      if self.left is None:
        self.left = Avltree(key)
      else:
        self.left.insertx(self, key)
    elif key > self.key:
      if self.right is None:
        self.right = Avltree(key)
      else:
        self.right.insertx(self, key)
    else:
      pass

  def insertx(self, p, key):
    node = self
    s = []
    while True:
      if node.key > key:
        s.append((node, -1))
        if node.left is None:
          node.left = Avltree(key)
          node = node.left
          break
        else:
          node = node.left
      elif node.key < key:
        s.append((node, 1))
        if node.right is None:
          node.right = Avltree(key)
          node = node.right
          break
        else:
          node = node.right
    while len(s) != 0:
      node, direct = s.pop()
      if len(s) != 0:
        par = s[-1][0]
      else:
        par = p
      if direct == -1:
        if node.balance == "Right":
          node.balance = "Even"
          break
        elif node.balance == "Even":
          node.balance = "Left"
        elif node.balance == "Left":
          if node.left.balance == "Right":
            node.replace(par, node.DoubleRightRotation())
          elif node.left.balance == "Left":
            node.replace(par, node.SingleRightRotation())
          break
      elif direct == 1:
        if node.balance == "Left":
          node.balance = "Even"
          break
        elif node.balance == "Even":
          node.balance = "Right"
        elif node.balance == "Right":
          if node.right.balance == "Left":
            node.replace(par, node.DoubleLeftRotation())
          elif node.right.balance == "Right":
            node.replace(par, node.SingleLeftRotation())
          break

  def to_s(self):
    return self.key
  def left_s(self):
    if self.left is None:
      return None
    return (self.left).key
  def right_s(self):
    if self.right is None:
      return None
    return (self.right).key

n=int(input())
a=list(map(int,input().split()))
ans=0
l=[0]*n
for i in range(n):
  l[a[i]-1]=i
root=Avltree()
for i in range(n):
  root.insert(l[i])
  ans+=(i+1)*(l[i]-root.search_lower(l[i],-1))*(root.search_higher(l[i],n)-l[i])
print(ans)