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(enumerate(list(map(int,input().split()))))
left = [i-1 for i in range(N)]
right = [i+1 for i in range(N)]
A.sort(key=lambda x:x[1],reverse=True)
ans = 0
for i,a in A:
    il,ir = left[i],right[i]
    ans += a*(i-il)*(ir-i)
    if ir<N:
        left[ir] = il
    if il>-1:
        right[il] = ir
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):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

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

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    a = [(int(x),i+1) for i,x in enumerate(sys.stdin.readline().split())]

    N0 = 2**(N.bit_length())
    st1 = [0] * (2*N0)
    st2 = [N+1] * (2*N0)

    def update_max(i,x):
        i += N0 - 1
        st1[i] = x
        while i > 0:
            i = (i-1) // 2
            st1[i] = max(st1[i*2+1],st1[i*2+2])

    def update_min(i,x):
        i += N0 - 1
        st2[i] = x
        while i > 0:
            i = (i-1) // 2
            st2[i] = min(st2[i*2+1],st2[i*2+2])

    def query_max(l,r):
        L = l + N0; R = r + N0
        ret = 0
        while L < R:
            if L % 2:
                ret = max(ret,st1[L-1])
                L += 1
            if R % 2:
                R -= 1
                ret = max(ret,st1[R-1])
            L //= 2; R //=2
        return ret

    def query_min(l,r):
        L = l + N0; R = r + N0
        ret = N+1
        while L < R:
            if L % 2:
                ret = min(ret,st2[L-1])
                L += 1
            if R % 2:
                R -= 1
                ret = min(ret,st2[R-1])
            L //= 2; R //= 2
        return ret

    a.sort()
    ans = 0
    for x,y in a:
        i = query_max(1,y)
        j = query_min(y,N+1)
        ans += (y-i) * (j-y) * x
        update_max(y,y)
        update_min(y,y)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 0
        s = 0
        step = 1 << self.size.bit_length()
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                print(self.bit[i + step - 1], i, step)
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
d=defaultdict(int)
for i in range(n):
  d[a[i]]=i+1
Bit = BinaryIndexedTree(n+1)
ans=0
for i in range(n):
  j=i+1
  i=d[j]
  x=Bit.sum(i)
  ok=i
  ng=-1
  while ok - ng > 1:
    mid=(ok+ng)//2
    if Bit.sum(mid)==x:
      ok=mid
    else:
      ng=mid
  l=ok+1
  ok=i
  ng=n+1
  while ng - ok > 1:
    mid=(ok+ng)//2
    if Bit.sum(mid)==x:
      ok=mid
    else:
      ng=mid
  r=ok
  ans+=j*(i-l+1)*(r-i+1)
  Bit.add(i,1)
print(ans)

Solution (Python):
class BinaryIndexedTree(): 
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def get(self, idx):
        return self.sum(idx) - self.sum(idx - 1)

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        if res >= self.n:
            return self.n
        return res + 1

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

D = [None for _ in range(N)]

for i in range(N):
    D[A[i] - 1] = i + 1

bit = BinaryIndexedTree(N + 1)

res = 0

for i in range(N):
    s = bit.sum(D[i])
    lt = bit.bisect_left(s)
    rt = bit.bisect_left(s + 1)
    bit.add(D[i], 1)
    res += (i + 1) * (D[i] - lt) * (rt - D[i])

print(res)

Solution (Python):
def main():
    import heapq
    N = int(input())
    a = list(map(int, input().split()))
    q = []
    LR = [[0, N-1] for i in range(N)]
    for i in range(N):
        x = a[i]
        while(q and -q[0][0] > x):
            v, id = heapq.heappop(q)
            LR[id][1] = i - 1
        heapq.heappush(q, (-x, i))

    for i in range(N-1, -1, -1):
        x = a[i]
        while(q and -q[0][0] > x):
            v, id = heapq.heappop(q)
            LR[id][0] = i+1
        heapq.heappush(q, (-x, i))
    ans = 0
    for i in range(N):
        ans += a[i] * (LR[i][1] - i + 1)*(i - LR[i][0] + 1)
    print(ans)


main()

Solution (Python):
N = int(input())
A = list(enumerate(list(map(int, input().split()))))
A = sorted(A, key=lambda x:x[1], reverse=True)

before_idx = list(range(-1, N-1)) + [-1]
next_idx = list(range(1, N+1)) + [N]

ans = 0
for i, a in A:
  il = before_idx[i]
  ir = next_idx[i]
  ans += (i - il) * (ir - i) * a
  before_idx[ir] = il
  next_idx[il] = ir

print (ans)

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(1,0),(-1,0),(0,1),(0,-1)];EightNb=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('EWNS',FourNb))
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()
 
class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: 
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    
    def query(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    
    def query_id(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)
 
class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]
 
    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
 
show_flg=False
show_flg=True
ans=0

n=I()
a=LI()
b=[0]*n
for i in range(n):
    b[a[i]-1]=i
    
st=SparseTable(a,init_func=min,init_idl=inf)

m=n.bit_length()
for j in range(n):
    b[j]
    l=r=b[j]
    for i in range(m)[::-1]:
        if r+(1<<i)<n and st.query(b[j],r+(1<<i)+1)>=j+1:
            r+=(1<<i)
        if l-(1<<i)>=0 and st.query(l-(1<<i),b[j]+1)>=j+1:
            l-=(1<<i)
    ans+=(r-b[j]+1)*(b[j]-l+1)*(j+1)

print(ans)

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


class SparseTable:
    def __init__(self, a, func=max, one=-10**18):
        self.table = [a[:]]
        self.n = len(a)
        self.logn = self.n.bit_length()
        self.func = func
        self.one = one

        for i in map(lambda x: 1 << x, range(self.logn - 1)):
            self.table.append([])
            for j in range(self.n - i * 2 + 1):
                self.table[-1].append(self.func(self.table[-2][j],
                                                self.table[-2][j + i]))

    def get_section(self, i, j):
        length = j - i
        log = length.bit_length() - 1
        if length <= 0:
            return self.one
        return self.func(self.table[log][i], self.table[log][j - (1 << log)])


sp = SparseTable(a)
ans = 0
for i in range(n):
    mi = 0
    ma = i
    while mi != ma:
        mm = (mi + ma) // 2
        if sp.get_section(mm, i) <= a[i]:
            ma = mm
        else:
            mi = mm + 1
    j = i - mi + 1

    mi = i - 1
    ma = n - 1
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        if sp.get_section(i, mm + 1) <= a[i]:
            mi = mm
        else:
            ma = mm - 1
    k = mi - i + 1
    ans += j * k * a[i]
print(-ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
a_to_i = {a: i for i, a in enumerate(A, start=1)}

L = list(range(-1, N + 1))
R = list(range(1, N + 3))

ans = 0
for a in reversed(range(1, N + 1)):
    i = a_to_i[a]
    ans += a * (R[i] - i) * (i - L[i])
    L[R[i]] = L[i]
    R[L[i]] = R[i]

print(ans)

Solution (Python):
import sys
class Node:
    def __init__(self, key, height):
        self.key = key 
        self.height = height 
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): 
        return self.size(self.left) - self.size(self.right)

    
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

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

    
    
    
    def rotateL(self, n): 
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): 
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    
    
    
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): 
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            t.value = value
            return t

    
    
    
    def delete(self, key): self.root = self.delete_sub(self.root, key)

    def delete_sub(self, t, key):
        if t is None:
            self.change = False
            return None
        if key < t.key:
            t.left = self.delete_sub(t.left, key)
            return self.balanceR(t)
        elif key > t.key:
            t.right - self.delete_sub(t.right, key)
            return self.balanceL(t)
        else:
            if t.left is None:
                self.change = True
                return t.right
            else:
                t.left = self.delete_max(t.left)
                t.key = self.lmax
                t.value = self.value
                return self.balanceR(t)
    
    def delete_max(self, n):
        if n.right is None: 
            self.change = True
            self.lmax = n.key
            self.value = n.value
            return n.left
        else:
            n.right = self.delete_max(n.right)
            return self.balanceL(n)

    
    
    
    def search(self, key, lower, higher):
        t = self.root
        lb, hb = lower, higher
        while t:
            if key < t.key:
                hb = t.key
                t = t.left
            else:
                lb = t.key
                t = t.right
        return lb, hb
                

def solve(): 
    N = int(input())
    A = [int(a) for a in input().split()]
    Ai = dict()
    for i, a in enumerate(A): Ai[a] = i
    Tree = AVLTree()
    ini = Ai[1]
    Ans = 1 * (ini + 1) * (N - ini)
    Tree.insert(ini)
    for i in range(2, N + 1):
        ai = Ai[i]
        l, r = Tree.search(ai, -1, N)
        Ans += i * (ai - l) * (r - ai)
        Tree.insert(ai)
    print(Ans)
        
    return 0

if __name__ == "__main__":
    solve()

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

Solution (Python):
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

I = list(range(N))
I.sort(key=lambda i: A[i], reverse=True)

V = set()
tree = UnionFind(N)

ans = 0
for i in I:
    a = A[i]
    L = tree.sizeOfSameRoot(i - 1) if (i - 1) in V else 0
    R = tree.sizeOfSameRoot(i + 1) if (i + 1) in V else 0
    ans += a * ((L + 1) * (R + 1))

    if i - 1 in V:
        tree.union(i - 1, i)
    if i + 1 in V:
        tree.union(i + 1, i)
    V.add(i)

print(ans)

Solution (Python):
import sys
from operator import itemgetter

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

print(ans)

Solution (Python):
import sys
from operator import itemgetter


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

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

    def put(self, i, x):
        while i <= self.size:
            self.tree[i] = self.func(self.tree[i], x)
            i += i & -i


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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = map(int, read().split())
ans = 0
l = list(range(n + 1))
r = list(range(n + 1))
memo = [0] * (n + 1)
for i, aa in enumerate(a):
    memo[aa] = i
for i in range(n, -1, -1):
    v = memo[i]
    ans += (v - l[v] + 1) * (r[v] - v + 1) * i
    l[r[v] + 1], r[l[v] - 1] = l[v], r[v]
print(ans)

Solution (Python):


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

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

    L = [-1] * (N + 2)
    R = [N] * (N + 2)
    for i in range(N):
        L[i] = i - 1
        R[i] = i + 1

    ans = 0
    for x, ind in zip(range(N, 0, -1), reversed(xtoi)):
        
        
        l1 = L[ind]
        r1 = R[ind]
        ans += x * (ind - l1) * (r1 - ind)
        L[r1] = l1
        R[l1] = r1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
a_to_i = {a: i for i, a in enumerate(A, start=1)}

L = [i - 1 for i in range(N + 2)]
R = [i + 1 for i in range(N + 2)]

ans = 0
for a in range(N, 0, -1):
    i = a_to_i[a]
    ans += a * (R[i] - i) * (i - L[i])
    L[R[i]] = L[i]
    R[L[i]] = R[i]

print(ans)

Solution (Python):
class BinaryIndexTree:  
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        if isinstance(N, int):
            self.N = N
            self.depth = N.bit_length()
            self.tree = [0] * (N + 1)
            self.elem = [0] * (N + 1)
        elif isinstance(N, list):
            self.N = len(N)
            self.depth = self.N.bit_length()
            self.tree = [0] + N
            self.elem = [0] + N
            self._init()
        else:
            raise "INVALID INPUT: input must be int or list"

    def _init(self):
        size = self.N + 1
        for i in range(1, self.N):
            if i + (i & -i) > size:
                continue
            self.tree[i + (i & -i)] += self.tree[i]

    def add(self, i, x):
        self.elem[i] += x
        while i <= self.N:
            self.tree[i] += x
            i += i & -i

    def sum(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def lower_bound(self, val):
        if val <= 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] < val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1


if __name__ == "__main__":
    N = int(input())
    P = list(map(int, input().split()))
    idx = {a: i for i, a in enumerate(P, start=1)}

    bit = BinaryIndexTree(N)
    ans = 0
    for i in range(1, N + 1):
        bit.add(idx[i], 1)
        s = bit.sum(idx[i])
        l = bit.lower_bound(s)-bit.lower_bound(s-1)
        r = bit.lower_bound(s+1) - idx[i]
        ans += i*l*r
    print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def solve():
    N = int(rl())
    a = list(map(int, rl().split()))
    
    b = [0] * (N + 1)
    for i, x in enumerate(a):
        b[x] = i
    
    uf = UnionFind(N)
    ans = 0
    for idx in b[:0:-1]:
        left, right = 1, 1
        if 0 <= idx - 1 and a[idx] < a[idx - 1]:
            left += uf.size(idx - 1)
            uf.union(idx - 1, idx)
        if idx + 1 <= N - 1 and a[idx] < a[idx + 1]:
            right += uf.size(idx + 1)
            uf.union(idx, idx + 1)
        ans += left * right * a[idx]
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

plc = [0 for i in range(n)]
for i in range(n):
  plc[a[i]-1] = i
ans = 0
uf = UnionFind(n)
for i in range(n)[::-1]:
  p = plc[i]
  x = i+1
  if p < n-1 and a[p] < a[p+1]:
    x *= uf.size(p+1)+1
    uf.union(p,p+1)
  if p > 0 and a[p-1] > a[p]:
    x *= uf.size(p-1)+1
    uf.union(p-1,p)
  ans += x
print(ans)