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):
from bisect import*
class SquareSkipList:
    def __init__(self,values=[],square=1000,seed=42):
        INF=10**18
        self.square=square
        self.layer1=layer1=[]
        self.layer0=layer0=[]
        y=seed
        l0=[]
        for v in values:
            y^=(y&0x7ffff)<<13
            y^=y>>17
            y^=(y&0x7ffffff)<<5
            if y%square<1:
                layer0+=l0,
                l0=[]
                layer1+=v,
            else:l0+=v,
        layer1+=INF,
        layer0+=l0,
        self.rand_y=y
    def add(self,x):
        y=self.rand_y
        y^=(y&0x7ffff)<<13
        y^=y>>17
        y^=(y&0x7ffffff)<<5
        self.rand_y=y
        if y%self.square<1:
            layer1,layer0=self.layer1,self.layer0
            idx1=bisect(layer1,x)
            layer1.insert(idx1,x)
            layer0_idx1=layer0[idx1]
            idx0=bisect(layer0_idx1,x)
            layer0.insert(idx1+1,layer0_idx1[idx0:])
            del layer0_idx1[idx0:]
        else:
            idx1=bisect(self.layer1,x)
            insort(self.layer0[idx1],x)
    def remove(self,x):
        layer1,layer0=self.layer1,self.layer0
        idx1=bisect_left(layer1,x)
        layer0_idx1=layer0[idx1]
        idx0=bisect_left(layer0_idx1,x)
        if idx0==len(layer0_idx1):
            del layer1[idx1]
            layer0[idx1]+=layer0.pop(idx1+1)
        else:del layer0_idx1[idx0]
    def search_higher(self,x):
        layer1,layer0=self.layer1,self.layer0
        idx1=bisect(layer1,x)
        layer0_idx1=layer0[idx1]
        idx0=bisect(layer0_idx1,x)
        return layer1[idx1]if idx0==len(layer0_idx1)else layer0_idx1[idx0]
    def search_lower(self,x):
        layer1,layer0=self.layer1,self.layer0
        idx1=bisect_left(layer1,x)
        layer0_idx1=layer0[idx1]
        idx0=bisect_left(layer0_idx1,x)
        return layer1[idx1-1]if idx0<1else layer0_idx1[idx0-1]
    def pop(self,idx):
        layer1,layer0=self.layer1,self.layer0
        s=-1
        for i,l0 in enumerate(layer0):
            s+=len(l0)+1
            if s>=idx:break
        if s==idx:
            layer0[i]+=layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:return layer0[i].pop(idx-s)
def main():
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    t=SquareSkipList([])
    t.add(0)
    t.add(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(t.search_higher(v)-v)*(v-t.search_lower(v))*i
        t.add(v)
    print(c)
main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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


class SegmentTree:
    """
    引数：
        N: 処理する区間の長さ
        operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
        UNIT: 単位元
        a: 長さNの配列 a で初期化（a を与えない場合、単位元で初期化）
    注意: 内部的には 1-indexed
    """

    def __init__(self, N, operator, unit, a=None):
        self.op = operator
        self.UNIT = unit

        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.UNIT]*(2*self.N0)
        if a != None:
            self.tree[self.N0:self.N0+N] = a[:]
            for k in range(self.N0-1, 0, -1):
                self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])

    
    def update(self, k, x):
        k += self.N0
        self.tree[k] = x
        k //= 2
        while k:
            self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
            k //= 2

    
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = self.UNIT
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(self.tree[R], s)
            if L & 1:
                s = self.op(s, self.tree[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get(self, k):  
        return self.tree[k + self.N0]

    def all(self):
        return self.tree[1]


seg_sml = SegmentTree(N, min, N)
seg_big = SegmentTree(N, max, -1)

ans = 0

for a in range(1, N + 1):
    i = idx[a]
    l = seg_big.query(0, i)
    r = seg_sml.query(i, N)

    left = i - l - 1
    right = r - i - 1

    cnt = (r - l - 1) * (r - l) // 2
    cnt -= left * (left + 1) // 2
    cnt -= right * (right + 1) // 2

    ans += cnt * a

    seg_sml.update(i, i)
    seg_big.update(i, i)


print(ans)

Solution (Python):
def main():
    N = int(input())
    a = list(map(int, input().split()))
    l = [-1] * N
    s = []
    for i, v in enumerate(a):
        while s and  s[-1][0] > v:
            s.pop()
        if s:
            l[i] = s[-1][1]
        s.append((v, i))
    r = [N] * N
    s = []
    for i, v in (enumerate(reversed(a))):
        while s and s[-1][0] > v:
            s.pop()
        if s:
            r[N - i - 1] = s[-1][1]
        s.append((v, N - i - 1))
    ans = 0
    for i in range(N):
        rr = r[i] - 1
        ll = l[i] + 1
        ans += ((rr - i + 1) * (i - ll) + rr - i)*a[i] + a[i]
    return ans
print(main())

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    L, R = [0] * N, [0] * N
    s = [(-1, -1)]
    for i, a in enumerate(A):
        while s[-1][0] >= a:
            s.pop()
        L[i] = i - s[-1][1]
        s.append((a, i))
    s = [(-1, N)]
    for i in reversed(range(N)):
        a = A[i]
        while s[-1][0] >= a:
            s.pop()
        R[i] = s[-1][1] - i
        s.append((a, i))
    return sum(a * l * r for a, l, r in zip(A, L, R))

print(main())

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()

def min_range(A):
    smaller = [[0, -1]]
    ret = []
    for i, a in enumerate(A):
        while smaller[-1][0] > a:
            smaller.pop()
        ret.append(i-smaller[-1][1])
        smaller.append([a, i])
    return ret

B = min_range(A)
C = min_range(A[::-1])[::-1]

answer = 0
for i in range(N):
    answer += A[i] * B[i] * C[i]

print(answer)

Solution (Python):
def examA():
    X = SI()
    d = defaultdict(int)
    for s in X:
        if s=="T" and d["S"]>=1:
            d["S"] -=1
        else:
            d[s] += 1
    ans = d["S"] + d["T"]
    print(ans)
    return

def examB():
    
    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  

        
        
        
        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
                return t

        
        
        

        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
    N = I()
    A = LI()
    lst = [0] * N
    for i in range(N):
        lst[A[i]-1] = i
    AVL = AVLTree()
    ans = 0
    for a in range(1,N+1):
        i = lst[a-1]
        l, r = AVL.search(i,-1,N)
        AVL.insert(i)
        
        ans += (i-l)*(r-i)*a
        
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB()

"""

"""

Solution (Python):




"""
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys"""





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

lst=[[A[0],0,1]]
count=0

for i in range(1,N):
    m=1
    while lst and lst[-1][0]>A[i]:
        a,b,c=lst.pop()
        count+=a*(i-b)*c
        m+=c
    lst.append([A[i],i,m])
while lst:
    a,b,c=lst.pop()
    count+=a*(N-b)*c

print(count)

Solution (Python):




from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys





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

lst=[[A[0],0,1]]
count=0

for i in range(1,N):
    m=1
    while lst and lst[-1][0]>A[i]:
        a,b,c=lst.pop()
        count+=a*(i-b)*c
        m+=c
    lst.append([A[i],i,m])
while lst:
    a,b,c=lst.pop()
    count+=a*(N-b)*c

print(count)

Solution (Python):




from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys





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

lst=[[A[0],0,1]]
count=0

for i in range(1,N):
    m=1
    while lst and lst[-1][0]>A[i]:
        a,b,c=lst.pop()
        count+=a*(i-b)*c
        m+=c
    lst.append([A[i],i,m])
while lst:
    a,b,c=lst.pop()
    count+=a*(N-b)*c

print(count)

Solution (Python):
import bisect
from collections import defaultdict
class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit
 
    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret
        
    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret
 
    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1:])
            self.child[i] = block[:sep]

def main():
    N = int(input())
    A = [int(i) for i in input().split()]

    
    IDX = defaultdict(int)
    for idx,a in enumerate(A):
        IDX[a] = idx

    SS = SqrtSet()
    SS.insert(-1)
    SS.insert(N)

    ans = 0
    for n in range(1, N + 1):
        H = SS.search_higher(IDX[n])
        L = SS.search_lower(IDX[n])
        ans += (IDX[n] - L) * (H - IDX[n]) *  n
        SS.insert(IDX[n])

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n = int(input())
a = [0] + list(map(int, input().split())) + [n + 1]

idx = [0] * (n + 2)
for i, e in enumerate(a):
    idx[e] = i

uf_l = UnionFind(n + 2)
uf_r = UnionFind(n + 2)

ans = 0
for num in range(n, 0, -1):
    i = idx[num]
    ans += num * (uf_l.get_size(i) * uf_r.get_size(i))
    uf_l.unite(i, i + 1)
    uf_r.unite(i, i - 1)

print(ans)

Solution (Python):
import sys
from bisect import bisect

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 

    
    
    
    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
            return t

    
    
    

    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():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    for i, p in enumerate(P): pindex[p - 1] = i

    Ans = (pindex[0] + 1) * (N - pindex[0])
    T = AVLTree()
    T.insert(pindex[0])
    for i in range(1, N):
        pid = pindex[i]
        l, r = T.search(pid, -1, N)
        Ans += (i + 1) * (pid - l) * (r - pid)
        T.insert(pid)      

    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import bisect


class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit

    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret
        
    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret

    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1:])
            self.child[i] = block[:sep]
                
    def dump(self):
        for b in self.child:
            print(len(b), end=" ")
        print("")
            
            
def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: p[i])
    t = SqrtSet()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in range(n):
        right = t.search_higher(idx[i])
        left = t.search_lower(idx[i])
        ans+=(i+1)*(idx[i]-left)*(right-idx[i])
        t.insert(idx[i])
        
    print(ans)


main()

Solution (Python):
import bisect


class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit

    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret
        
    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret

    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1:])
            self.child[i] = block[:sep]
                
    def dump(self):
        for b in self.child:
            print(len(b), end=" ")
        print("")
            
            
def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: p[i])
    t = SqrtSet()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in range(n):
        right = t.search_higher(idx[i])
        left = t.search_lower(idx[i])
        ans+=(i+1)*(idx[i]-left)*(right-idx[i])
        t.insert(idx[i])
        
    print(ans)


main()

Solution (Python):
import random
import time




def rotate(nd, d):
    c = nd[d]
    if d:
        e = c[1]
        nd[1] = c[0]
        c[0] = nd
    else:
        e = c[0]
        nd[0] = c[1]
        c[1] = nd

    r = c[4] = nd[4]
    nd[4] = r - (e[4] if e else 0) - 1
    return c


root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]

    
    nd = [None, None, val, pri, 1]
    while st:
        x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] += 1
        if x[3] >= nd[3]:
            break
        rotate(x, d)
    else:
        root = nd

    for x in st:
        x[4] += 1

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] -= 1
    return x

def delete(val):
    global root
    x = root

    st = []
    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        st.append(y)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
        for x in st:
            x[4] -= 1
    else:
        root = __delete(x)

def find(val):
    global root
    x = root
    while x:
        if val == x[2]:
            return 1
        x = x[x[2] < val]
    return 0

def search1(val):
    global root
    x = root
    ans=-1
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            ans=max(ans,x[2])
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans

def search2(val):
    global root
    x=root
    ans=10**20
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            ans=min(ans,x[2])
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans



N=int(input())
A=list(map(int,input().split()))
A=[A[i]-1 for i in range(0,N)]
function=[0 for i in range(0,N)]
for i in range(0,N):
    function[A[i]]=i

random.seed()
randint=random.randint

insert(function[0],randint(1,200000))
data1=[0 for i in range(0,N)]
data2=[0 for i in range(0,N)]
data1[0]=-1
data2[0]=N
for i in range(1,N):
    if search1(function[i])!=-1:
        data1[i]=search1(function[i])
    else:
        data1[i]=-1
    if search2(function[i])!=10**20:
        data2[i]=search2(function[i])
    else:
        data2[i]=N
    insert(function[i],randint(1,200000))

ans=0
for i in range(0,N):
    prod=(function[i]-data1[i])*(data2[i]-function[i])
    ans+=prod*(i+1)

print(ans)

Solution (Python):


class BIT:
    def __init__(self, n, init_list):
        self.num = n+1
        self.tree = [0]*self.num
        for i,e in enumerate(init_list):
            self.update(i,e)

    def update(self,k,x):
        k = k+1
        while k < self.num:
            self.tree[k] += x
            k += (k&(-k))
        return 
    
    
    def query(self, l,r):
        ret = 0
        while r>0:
            ret += self.tree[r]
            r -= r&(-r)
        while l>0:
            ret -= self.tree[l]
            l -= l&(-l)
        
        return ret


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

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


ans = 0
seg = BIT(N,[0]*N)

def judge(l,r):
    if l>r:
        l,r = r,l
    res = seg.query(l,r+1)
    if res:
        return False
    else:
        return True


for idx in idxlist:    
    ng_l = -1
    ng_r = N
    left = idx
    while abs(left-ng_l)>1:
        mid = (left+ng_l)//2
        if judge(idx,mid):
            left = mid
        else:
            ng_l = mid
    
    right = idx
    while abs(ng_r-right)>1:
        mid = (right+ng_r)//2
        if judge(idx,mid):
            right = mid
        else:
            ng_r = mid
    
    ans += A[idx]*(idx-left+1)*(right-idx+1)
    seg.update(idx,1)
    
print(ans)

Solution (Python):
class BinaryIndexedTree:
    def __init__(self, N, f=max, id=0):
        self.N = N
        self.bit = [id] * (self.N+1)
        self.f = f
        self.id = id

    def query(self, i):
        res = self.id
        while i > 0:
            res = self.f(res, self.bit[i])
            i -= i & -i
        return res

    def update(self, i, x):
        while i <= self.N:
            self.bit[i] = self.f(self.bit[i], x)
            i += i & -i

def main():
    N,*A=map(int, open(0).read().split())
    L,R=[0]*N,[0]*N
    bit=BinaryIndexedTree(N, max, -1)
    for i,a in enumerate(A):
        L[a-1]=i-bit.query(a)
        bit.update(a, i)
    bit=BinaryIndexedTree(N, max, -1)
    for i,a in enumerate(A[::-1]):
        R[a-1]=i-bit.query(a)
        bit.update(a, i)
    print(sum(L[i]*R[i]*(i+1) for i in range(N)))

if __name__ == "__main__":
    main()

Solution (Python):
class BIT:
  def __init__(self,n):
    self.N = n
    self.data = [0]*(N+1)
  def bit_add(self,i,a):
    j = i+1
    while j<=N:
      self.data[j] += a
      j += j&-j
  def bit_sum(self,i):
    m = 0
    j = i+1
    while j>0:
      m += self.data[j]
      j -= j&-j
    return m
  def bit_search(self,x):
    i = 0
    m = 0
    j = 1<<(self.N.bit_length()-1)
    while j:
      if i+j<=N and self.data[i+j]+m<=x:
        i += j
        m += self.data[i]
      j >>= 1
    return i
N, *A = map(int, open(0).read().split())
bit = BIT(N)
ntoi = [0]*(N+1)
ans = 0
for i, a in enumerate(A):
  ntoi[a] = i
for i in range(1,N+1):
  j = ntoi[i]
  L = bit.bit_sum(j)
  R = N-L-1
  if L!=0:
    a = bit.bit_search(L-1)
  else:
    a = -1
  if R!=0:
    b = bit.bit_search(L)
  else:
    b = N
  ans += (j-a)*(b-j)*i
  bit.bit_add(j,1)
print(ans)

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

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

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