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
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

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


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

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

ans = 0
for i in reversed(range(1, N+1)):
    ind = pos[i]
    left = 0
    right = 0
    if ind > 0 and A[ind] < A[ind-1]:
        left = Un.size[Un.find(ind-1)]
        Un.union(ind, ind-1)
    if ind+1 < N and A[ind+1] > A[ind]:
        right = Un.size[Un.find(ind+1)]
        Un.union(ind, ind+1)
    ans += (left+1)*(right+1)*A[ind]

print(ans)

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 = [int(i) for i in 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):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
import heapq
n=int(input())
A=list(map(int,input().split()))
idx={}
for i,a in enumerate(A):
    idx[a]=i
hq=[]
right=[n-1]*n
for i in range(n):
    while hq and -hq[0]>A[i]:
        h=-heapq.heappop(hq)
        right[idx[h]]=i-1
    heapq.heappush(hq,-A[i])
hq=[]
left=[0]*n
for i in range(n-1,-1,-1):
    while hq and -hq[0]>A[i]:
        h=-heapq.heappop(hq)
        left[idx[h]]=i+1
    heapq.heappush(hq,-A[i])
ans=0
for i in range(n):
    ans+=A[i]*(i-left[i]+1)*(right[i]-i+1)
print(ans)

Solution (Python):
import heapq

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


d = {}
for i, ai in enumerate(a):
    d[ai] = i

h = []


right = [n-1] * n


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

h = []
left = [0] * n

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

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

print(ans)

Solution (Python):
import heapq


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

d = {}
for i, a_ in enumerate(a):
    d[a_] = i


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

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

h = []
left = [0] * n

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

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

print(ans)

Solution (Python):

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


def unite(x,y):
    x = find(x)
    y = find(y)
    
    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


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


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

par = [0]*n 
for i in range(n):
    par[i] = i
rank = [1]*n 
size = [1]*n 

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

ans = 0
for i in range(n,0,-1):
    k = b[i]
    left = 0
    right = 0
    if k-1>=0 and a[k-1]>a[k]:
        left =  size[find(k-1)]
        unite(k-1,k)
    if k+1<=n-1 and a[k+1]>a[k]:
        right = size[find(k+1)]
        unite(k+1,k)
    ans += (left+1)*(right+1)*a[k]

print(ans)

Solution (Python):

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


def unite(x,y,par,rank,size):
    x = find(x,par)
    y = find(y,par)
    
    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


def same(x,y,par):
    return find(x,par) == find(y,par)


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

par = [0]*n 
for i in range(n):
    par[i] = i
rank = [1]*n 
size = [1]*n 

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

ans = 0
for i in range(n,0,-1):
    k = b[i]
    left = 0
    right = 0
    if k-1>=0 and a[k-1]>a[k]:
        left =  size[find(k-1,par)]
        unite(k-1,k,par,rank,size)
    if k+1<=n-1 and a[k+1]>a[k]:
        right = size[find(k+1,par)]
        unite(k+1,k,par,rank,size)
    ans += (left+1)*(right+1)*a[k]

print(ans)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
b,l,r,ans = [0]*(n+1),[i for i in range(n+2)],[i for i in range(n+2)],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 = [int(_) for _ in input().split()]
left = list(range(N + 2))
right = list(range(N + 2))
index = {A[i - 1]: i for i in range(1, N + 1)}
ans = 0
for a in range(N, 0, -1):
    i = index[a]
    l = left[i]
    r = right[i]
    ans += a * (i - l + 1) * (r - i + 1)
    left[r + 1] = l
    right[l - 1] = r
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
index = [[] for _ in range(n+1)]
for i in range(n):
	index[a[i]] = i

l = list(range(n))
r = list(range(n))

ans = 0
for i in range(n, 0, -1):
	m = index[i]
	ans += i * (r[m] - m + 1) * (m - l[m] + 1)
	if l[m] > 0:
		r[l[m] - 1] = r[m]
	if r[m] < n-1:
		l[r[m] + 1] = l[m]

print(ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
N = int(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)

Solution (Python):
N=int(input())
a=[int(i) for i in input().split()]

def f(A):
  P=[0]*N
  S=[(-1,0)]
  for i,b in enumerate(A):
    while S[-1][1]>b:
      S.pop()
    P[b-1]=i-S[-1][0]
    S.append((i,b))
  return P
P=f(a)
Q=f(a[::-1])
ans=0
for i in range(N):
  ans+=(i+1)*P[i]*Q[i]
print(ans)

Solution (Python):
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(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))]))

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

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

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):
import heapq

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

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

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

q = []
heapq.heapify(q)
left = [0] * N
for i,a in reversed(list(enumerate(A))):
    while q and -q[0] > a:
        v = -heapq.heappop(q)
        left[v-1] = i+1
    heapq.heappush(q,-a)

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

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
b,l,r,ans = [0]*(n+1),[i for i in range(n+2)],[i for i in range(n+2)],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 = list(map(int, input().split()))
idx = {v: i for i, v in enumerate(A)}

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)

Solution (Python):
class _UnionFind:
    __slots__ = ['id']
    def __init__(self, n):
        self.id = [-1] * n
    def find(self, x):
        if self.id[x] < 0:
            return x
        else:
            self.id[x] = self.find(self.id[x])
            return self.id[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        res = self.id[x] * self.id[y]
        self.id[x] += self.id[y]
        self.id[y] = x
        return res

N, *A = map(int, open(0).read().split())
uf = _UnionFind(N)
idx = {A[i]: i for i in range(N)}
ans = 0
for a in range(N, 0, -1):
    i = idx[a]
    ans += a
    if i - 1 >= 0 and A[i - 1] > A[i]:
        ans += uf.union(i - 1, i) * a
    if i + 1 < N and A[i + 1] > A[i]:
        ans += uf.union(i + 1, i) * a
print(ans)

Solution (Python):
N, *A = map(int, open(0).read().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)

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

def f(l):
    p=[0]*(n+1)
    s=[(-1,0)] 
    for i,a in enumerate(l):
        while s[-1][1]>a: 
            s.pop()
        t=i-s[-1][0] 
        p[a]=t 
        s.extend([(i,a)]) 
    return p
p=f(l) 
q=f(l[::-1]) 
print(sum(i*p[i]*q[i] for i in l))

Solution (Python):

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

n = ni()
a = li()


dic = {}
for i, ai in enumerate(a):
    dic[ai] = i
    

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

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

print(ans)

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
def f(A):
    P=[0]*(N+1)
    S=[(-1,0)]
    for i,a in enumerate(A):
        while S[-1][1]>a:
            S.pop()
        t=i-S[-1][0]
        P[a]=t
        S.append((i,a))
    return P
P=f(A)
Q=f(A[::-1])
print(sum(a*P[a]*Q[a] for a in A))

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
def f(A):
    P=[0]*(N+1)
    S=[(-1,0)]
    for i,a in enumerate(A):
        while S[-1][1]>a:
            S.pop()
        t=i-S[-1][0]
        P[a]=t
        S.append((i,a))
    return P
P=f(A)
Q=f(A[::-1])
print(sum(a*P[a]*Q[a] for a in A))

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

    l, r = [-1 for i in range(n)], [n for i in range(n)]
    for i in range(n):
        if i == 0:
            continue
        elif a[i] > a[i-1]:
            l[i] = i - 1
        else:
            idx = l[i-1]
            while idx != -1 and a[i] < a[idx]:
                idx = l[idx]
            l[i] = idx

    for i in range(n-1, -1, -1):
        if i == n-1:
            continue
        elif a[i] > a[i+1]:
            r[i] = i + 1
        else:
            idx = r[i+1]
            while idx != n and a[i] < a[idx]:
                idx = r[idx]
            r[i] = idx

    ans = 0
    for i in range(n):
        ans += a[i] * (i-l[i]) * (r[i]-i)

    print(ans)


if __name__ == '__main__':
    main()

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

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    self.size = [1] * (len(self.elements)+1)
    for e in self.elements:
      self._root[e] = e
    
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    res = self.size[x] + 1
    self.size[x] += self.size[y]
    
    if x != y:
      self._root[y] = x
      
    return res
    
  def root(self, x):
    if self._root[x] != x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]

B = [0] * (n+1)

for i, a in zip(range(1, n+1), A):
    B[a] = i

uf = UnionFind(range(1, n+1))
ans = 0
A.insert(0, 0)

for j in range(n, 0, -1):
    i = B[j]
    left = 1
    right = 1

    if i - 1 >= 1 and A[i-1] > A[i]:
        left = uf.unite(i-1, i)

    if i + 1 <= n and A[i+1] > A[i]:
        right = uf.unite(i+1, i)
    
    ans += right * left * A[i]

print(ans)

Solution (Python):
from bisect import bisect

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

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    self.size = [1] * (len(self.elements)+1)
    for e in self.elements:
      self._root[e] = e
    
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    res = self.size[x] * self.size[y]
    self.size[x] += self.size[y]
    
    if x != y:
      self._root[y] = x

    return res
    
  def root(self, x):
    if self._root[x] != x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]

B = [0] * (n+1)

for i, a in zip(range(1, n+1), A):
    B[a] = i

uf = UnionFind(range(1, n+1))
ans = 0
A.insert(0, 0)

for j in range(n, 0, -1):
    i = B[j]
    ans += A[i]

    if i - 1 >= 1 and A[i-1] > A[i]:
        ans += uf.unite(i-1, i) * A[i]

    if i + 1 <= n and A[i+1] > A[i]:
        ans += uf.unite(i+1, i) * A[i]

print(ans)

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

order = [0]*(N+1)

for i in range(N):
    order[a[i]] = i

ans = 0
checkR = list(range(N+1))
checkL = list(range(N+1))

for i in range(N, 0, -1):
    ans += i*(order[i] - checkR[order[i]] + 1)*(checkL[order[i]] - order[i]+1)
    checkR[checkL[order[i]]+1] = checkR[order[i]]
    checkL[checkR[order[i]]-1] = checkL[order[i]]
print(ans)

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

d = [0] * (N+1)
for i in range(N):
    d[a[i]] = i

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

ans = 0
for i in range(N, 0, -1):
    di = d[i]
    ans += i * (right[di]-di+1) * (di-left[di]+1)
    right[left[di] - 1] = right[di]
    left[right[di] + 1] = left[di]

print(ans)

Solution (Python):

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

b = [None] * (N + 1)
for i, x in enumerate(a):
    b[x] = i

ans = 0
l_idx = list(range(N + 1))
r_idx = list(range(N + 1))
for i, p in reversed(list(enumerate(b))[1:]):
    l, r = l_idx[p], r_idx[p]
    ans += i * (p - l + 1) * (r - p + 1)
    l_idx[r + 1] = l
    r_idx[l - 1] = r

print(ans)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


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

    idx = {}
    for i in range(N):
        idx[a[i]] = i

    left_idx, right_idx = list(range(N + 1)), list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        i = idx[a]
        l, r = left_idx[i], right_idx[i]
        ans += (i - l + 1) * (r - i + 1) * a

        left_idx[r + 1] = l
        right_idx[l - 1] = r

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


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

    idx = {}
    for i in range(N):
        idx[a[i]] = i

    ans = 0
    left_idx, right_idx = list(range(N + 2)), list(range(N + 2))
    for a in range(N, 0, -1):
        i = idx[a]
        l, r = left_idx[i], right_idx[i]

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


from collections import defaultdict

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

cnt = 0
d = [0] * (N + 2)
for i in range(N):
    d[a[i]] = i


l = list(range(N + 2))
r = list(range(N + 2))


for i in range(N, 0, -1):
    di = d[i]
    cnt += i * (r[di] - di + 1) * (di - l[di] + 1)
    r[l[di] - 1] = r[di]
    l[r[di] + 1] = l[di]
    
    
    


print(cnt)

Solution (Python):
n=int(raw_input())
a=map(int,raw_input().split())
def f():
    s=[(0,-1)]
    x=[0]*(n+1)
    for i,j in enumerate(a):
        while s[-1][0]>j:s.pop()
        x[j]=i-s[-1][1]
        s.append((j,i))
    return x
l=f()
a.reverse()
r=f()
print sum([i*l[i]*r[i] for i in a])

Solution (Python):








par = [0]*202020
size = [0]*202020

def find(x):
	if par[x] == x:
		return x
	else:
		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


n = int(input())
for i in range(202020):
	par[i] = i
	size[i] = 1

a = [0] + list(map(int, input().split()))
b = [0]*(n+1)
for i in range(1, n+1):
	b[a[i]] = i

ans = 0
for j in reversed(range(1, n+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):
input()
A=map(int,raw_input().split())
def f():
 s=[(0,-1)];p=A*2
 for i,a in enumerate(A):
  while a<s[-1][0]:s.pop()
  p[a]=i-s[-1][1];s+=[(a,i)]
 return p
l=f()
A.reverse()
r=f()
print sum(a*l[a]*r[a]for a in A)

Solution (Python):
class UnionFind:
    def __init__(self,size):
        self.parent=range(size)
        self.tree_num=size
        self.tree_w=[1]*size
        self.rank=[0]*size

    def findset(self,x):
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.findset(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x=self.findset(x)
        y=self.findset(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.parent[x]=y
            self.tree_num-=1
            self.tree_w[y]+=self.tree_w[x]
        else:
            self.parent[y]=x
            self.tree_num-=1
            self.tree_w[x]+=self.tree_w[y]
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def tree_weight(self,x):
        return self.tree_w[self.findset(x)]

n=int(raw_input())
a=map(int,raw_input().split())
p=[0]*(n+1)
for i in xrange(n):
    p[a[i]]=i

uf=UnionFind(n+1)
ans=0
for j in xrange(n,0,-1):
    i=p[j]
    tmp=1
    if i>=1 and a[i]<a[i-1]:
        tmp*=uf.tree_weight(a[i-1])+1
        uf.unite(a[i],a[i-1])
    if i<n-1 and a[i]<a[i+1]:
        tmp*=uf.tree_weight(a[i+1])+1
        uf.unite(a[i],a[i+1])
    ans+=j*tmp
print(ans)

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

Solution (Python):
ss = raw_input()
X=map(int, raw_input().split(' '))
N = []
S = []

dR = dict()
for n in range(len(X)) + [len(X)]:
    if n >= len(X): k = -100
    else: 
        
        k = X[n]
    while len(S) > 0 and k < S[-1][1]:
        dR[S[-1][0]] = n - S[-1][0]
        S.pop()

    S.append((n, k))

dL = dict()
for n in list(reversed(range(len(X)))) + [-1]:
    if n < 0: k = -100
    else: 
        k = X[n]
    while len(S) > 0 and k < S[-1][1]:
        dL[S[-1][0]] = abs(n - S[-1][0])
        S.pop()
    S.append((n, k))


ts = 0
for n in xrange(len(X)):
    left = dL[n]
    right = dR[n]
    ts += ((left-1) * (right-1) + left + right - 1) * X[n]

print ts

Solution (Python):
from sys import stdin
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split())
    L = range(n + 2)
    R = range(n + 2)
    b = [0] * (n + 2)
    L[n+1] = R[n+1] = n
    L[0] = R[0] = 1
    for i, x in enumerate(a, 1):
        b[x] = i
    s = 0
    for i in xrange(n, 0, -1):
        j = b[i]
        s += i * (R[j] - j + 1) * (j - L[j] + 1)
        R[L[j]-1] = R[j]
        L[R[j]+1] = L[j]
    print s
main()

Solution (Python):

import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N = int(raw_input())
a = map(int, raw_input().split())

aso = [N]*N
q = [a[0]]
for i in xrange(1, N):
    while q and q[-1] > a[i]:
        aso[q[-1] - 1] = i
        q.pop()
    q.append(a[i])
dso = [-1]*N
q = [a[-1]]
for i in xrange(N - 2, -1, -1):
    while q and q[-1] > a[i]:
        dso[q[-1] - 1] = i 
        q.pop()
    q.append(a[i])

ans = 0
for i in xrange(N):
    ans += a[i] * (aso[a[i] - 1] - i)*(i - dso[a[i] - 1])
print ans