Problem:
 Score : 400 points    Problem Statement One day, Snuke was given a permutation of length N , a_1, a_2, ..., a_N , from his friend.  Find the following:       Constraints  1 ≦ N ≦ 200,000  (a_1, a_2, ..., a_N) is a permutation of (1, 2, ..., N) .         Input The input is given from Standard Input in the following format:  N  a_1  a_2  ...  a_N       Output Print the answer.  Note that the answer may not fit into a 32-bit integer.        Sample Input 1 3
2 1 3      Sample Output 1 9       Sample Input 2 4
1 3 2 4      Sample Output 2 19       Sample Input 3 8
5 4 8 1 2 6 7 3      Sample Output 3 85

Solution (Python):


import sys

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_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok


def calc1(m):
    cnt = lend - bit.sum(m)
    return cnt < 1


def calc2(m):
    cnt = bit.sum(m) - rstart
    return cnt >= 1

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]
    
    lend = bit.sum(idx)
    rstart = bit.sum(idx)
    
    l = bisearch_min(-1, idx, calc1) + 1
    
    r = bisearch_min(idx, N+1, calc2) - 1
    
    ans[a] = (idx-l+1) * (r-idx+1) * a
    
    bit.add(idx, 1)

print(sum(ans))

Solution (Python):
class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def build(self, data):
        pass

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

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

    def bisect_left(self, w):
        
        
        if w <= 0:
            return 0
        idx = 0  
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1

    def bisect_right(self, w):
        
        
        if w < 0:
            return 0
        idx = 0  
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] <= w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


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

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

ans = 0
bit = BIT1(n)
for x in range(1, n + 1):
    idx = a2idx[x]
    bit.add(idx, 1)
    idx_rank = bit.sum(idx)
    idx_l = bit.bisect_left(idx_rank - 1)
    idx_r = bit.bisect_left(idx_rank + 1)

    ans += x * (idx - idx_l) * (idx_r - idx)
    

print(ans)

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 main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * (N + 1)
    for i in range(N):
        B[A[i]] = i

    uni = UnionFind(N)
    ans = 0
    for i in range(N, 0, -1):
        k = B[i]
        left = 0
        right = 0
        if k - 1 >= 0 and A[k-1] > A[k]:
            left = uni.size(uni.find(k-1))
            uni.union(k-1,k)
        if k + 1 <= N - 1 and A[k+1] > A[k]:
            right = uni.size(uni.find(k+1))
            uni.union(k+1,k)

        ans += (left+1) * (right+1) * A[k]

    print(ans)




if __name__ == "__main__":
    main()

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 functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
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


n = I()
A = [0] + LI() + [0]
val_ind = {A[j]: j for j in range(n + 2)}
l = {i:i - 1 for i in range(1, n + 1)}
r = {i:i + 1 for i in range(1, n + 1)}
ans = 0
for k in range(n, 0, -1):
    k_ind = val_ind[k]
    l1 = l[k_ind]
    r1 = r[k_ind]
    ans += (k_ind - l1) * (r1 - k_ind) * k
    r[l1] = r1
    l[r1] = l1



print(ans)