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

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

Solution (Python):


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 
r = [0]*n 
ans = 0


for x in range(1,n+1)[::-1]:
    
    
    i = lst[x]

    
    if i+1 < n and a[i+1] > x:
        
        
        R = r[i+1]
    else:
        
        R = i
    
    
    if i-1 >= 0 and a[i-1] > x:
        
        
        L = l[i-1]
    else:
        
        L = i
    
    
    
    
    l[R] = L
    r[L] = R
    ans += (i-L+1)*(R-i+1)*x
print(ans)

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

Solution (Python):
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)]  
    R = [i for i in range(n+2)]  
    ans = 0
    for i, j in a:  
        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()

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

    class unionfind():
        
        def __init__(self, size):  
            self.size = size
            self.tree = [i for i in range(self.size)]  

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

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

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

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

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

        
        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 = [None] * N
    l_indexes = [None] * N


    
    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

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

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

Solution (Python):
N = int(input())
*A, = map(int,input().split())
 
P = [0]*N
for i,a in enumerate(A):
    P[a-1] = i
 
class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
        self.Min = [-1]*N
        self.Max = [-1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def get_min(self,n):
        p = self.get_Parent(n)
        return self.Min[p]
    def get_max(self,n):
        p = self.get_Parent(n)
        return self.Max[p]
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y: 
            self.Min[x] = min(self.Min[x],self.Min[y])
            self.Max[x] = max(self.Max[x],self.Max[y])
            self.Parent[y] = x
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)
    def create(self,n):
        if self.Min[n] == -1:
            self.Min[n] = n
            self.Max[n] = n
 
T = UnionFind(N)
ans = 0
for i in range(N-1,-1,-1):
    p = P[i]
    T.create(p)
    if p-1>=0 and T.get_min(p-1)!=-1:
        T.merge(p,p-1)
    if p+1<N and T.get_min(p+1)!=-1:
        T.merge(p,p+1)
    ans += (i+1)*(p-T.get_min(p)+1)*(T.get_max(p)-p+1)
print(ans)

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

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())
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(ans)

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

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

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

Solution (Python):
from heapq import heappush, heappop

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

b = [N] * N
c = [-1] * N

h = []
for i in range(N) :
    while len(h) > 0 and -h[0][0] > a[i] :
        b[h[0][1]] = i
        heappop(h)
    heappush(h, (-a[i], i))

h = []
for i in range(N - 1, -1, -1) :
    while len(h) > 0 and -h[0][0] > a[i] :
        c[h[0][1]] = i
        heappop(h)
    heappush(h, (-a[i], i))

ret = 0
for i in range(N) :
    ret += a[i] * (b[i] - i) * (i - c[i])
print(ret)

Solution (Python):


import sys

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

class BIT:

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

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

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

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res
    
    def bisearch_left(self, l, r, x):
        """ 区間l,rで左からx番目の値がある位置 """
        l_val = self.sum(l)
        ok = r
        ng = l
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_val >= x:
                ok = mid
            else:
                ng = mid
        return ok

    def bisearch_right(self, l, r, x):
        """ 区間l,rで右からx番目の値がある位置 """
        r_val = self.sum(r)
        ok = r
        ng = l
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if r_val - self.sum(mid) < x:
                ok = mid
            else:
                ng = mid
        return ok

N = INT()
A = LIST()

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

bit = BIT(N+2)

bit.add(0, 1)
bit.add(N+1, 1)
ans = [0] * (N+1)
for a in range(1, N+1):
    
    idx = idxs[a]
    
    l = bit.bisearch_right(-1, idx, 1) + 1
    
    r = bit.bisearch_left(idx, N+1, 1) - 1
    
    ans[a] = (idx-l+1) * (r-idx+1) * a
    
    bit.add(idx, 1)

print(sum(ans))