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



Sample input:
3
2 1 3


Sample output:
9

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
a = list(map(int,input().split()))
b = [0]*(N+1)
left,right = [i for i in range(N+2)],[i for i in range(N+2)]
ans = 0
for i in range(N):
    b[a[i]] = i
for i in range(N+1)[::-1]:
    m = b[i]
    l,r = left[m],right[m]
    ans += i*(m-l+1)*(r-m+1)
    left[r+1]=l
    right[l-1]=r
print(ans)

Submission status: Accepted

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

Ans=[0]*n
Ans[0]=1
Stack=[[A[0],1]]
for i in range(1,n):
  a=A[i]
  b,ct_b=Stack.pop()
  ct=1
  while b>a and Stack:
    ct+=ct_b
    b,ct_b=Stack.pop()
  if b<a:
    Stack.append([b,ct_b])
    Stack.append([a,ct])
  else:
    Stack.append([a,ct+ct_b])
    ct+=ct_b
  Ans[i]=ct
RA=A[::-1]
Ans_R=[0]*n
Ans_R[0]=1
Stack=[[RA[0],1]]
for i in range(1,n):
  a=RA[i]
  b,ct_b=Stack.pop()
  ct=1
  while b>a and Stack:
    ct+=ct_b
    b,ct_b=Stack.pop()
  if b<a:
    Stack.append([b,ct_b])
    Stack.append([a,ct])
  else:
    Stack.append([a,ct+ct_b])
    ct+=ct_b
  Ans_R[i]=ct  
Ans_R=Ans_R[::-1]
ans=0
for i in range(n):
  ans+=(A[i]*Ans[i]*Ans_R[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
class DammyMap:
    #1-indexed
    def __init__(self, A, B, issum = False):
        #Aに初期状態の要素をすべて入れる,Bは値域のリスト
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        if issum:
            self.sumtree = [0] * (self.size + 1)
            Ssum = [0] + list(accumulate([CA[self.X[i]]*self.X[i] for i in range(self.size)]))
            for i in range(1, 1+self.size):
                self.sumtree[i] = Ssum[i] - Ssum[i - (i&-i)]
    def compress(self, L):
        #座圧
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        # 1-indexed
        return L2, C
    
    def leng(self):
        #今入っている個数を取得
        return self.count(self.size)
    
    def count(self, i):
        #i(Bの元)以下の個数を取得
        i = self.comp[i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        #v(Bの元である必要はない)未満の個数を取得
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        #v(Bの元である必要はない)以下の個数を取得
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        #iをx個入れる,負のxで取り出す,iの個数以上取り出すとエラーを出さずにバグる
        i = self.comp[i]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        
        
    def get(self, v):
        # v番目の値を取得
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s]
            k //= 2
        return self.X[s]
    
    def addsum(self, i, x):
        #sumを扱いたいときにaddと併用
        x *= i
        i = self.comp[i]
        while i <= self.size:
            self.sumtree[i] += x
            i += i & -i
    
    def countsum(self, i):
        #i(Bの元)以下のsumを取得
        i = self.comp[i]
        s = 0
        while i > 0:
            s += self.sumtree[i]
            i -= i & -i
        return s
    
    def getsum(self, v):
        #v番目までのsumを取得
        x = self.get(v)
        return self.countsum(x) - x*(self.count(x) - v)


N = int(input())
A = list(map(int, input().split()))
B = {v : i for i, v in enumerate(A, 1)}
T = DammyMap([0, N+1], list(range(0, N+2)))
ans = 0
for a in range(1, N+1):
    b = B[a]
    T.add(b, 1)
    i = T.count(b)
    ans += a*(T.get(i+1)-b)*(b-T.get(i-1))
print(ans)

Submission status: Accepted

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

l=[]
r=[]
s=[]

for i,x in enumerate(a):
  left=i
  while len(s)>0 and x<s[-1][0]:
    left=s[-1][-1]
    s.pop()
  l.append(left)
  s.append([x,left])
  #print(l)
  #print(s)
s=[]
for i in range(N-1,-1,-1):
  right=i
  x=a[i]
  while len(s)>0 and x<s[-1][0]:
    right=s[-1][-1]
    s.pop()
  r.append(right)
  s.append([x,right])
r=r[::-1]
ans=0
for i,(x,le,ri) in enumerate(zip(a,l,r)):
  ans+=x*(i-le+1)*(ri-i+1)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

b=[i for i in range(1,N+1)]

A=[]
for i in range(N):
    A.append([a[i],b[i]])
A.sort(reverse=True)
#print(A)
PL=[i for i in range(N+1)]+[N+1]
PR=[i for i in range(N+1)]+[N+1]

def findL(x):
    if x==PL[x]:
        return x
    else:
        return findL(PL[x])
        
def findR(x):
    if x==PR[x]:
        return x
    else:
        return findR(PR[x])
#print(PR)
ans=0
for i in range(N):
    ans+=A[i][0]*(A[i][1]-findL(A[i][1]-1))*(findR(A[i][1]+1)-A[i][1])
    #print(ans,A[i][1],(A[i][1]-findL(A[i][1])+1),findR(A[i][1])-A[i][1]+1)
    #print(PR)
    PL[A[i][1]]=findL(A[i][1]-1)
    PR[A[i][1]]=findR(A[i][1]+1)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

ad = {}
for i, a in enumerate(alist):
  ad[a] = i

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

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

h = []
left = [0] * n

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
d = {}
for i,j in enumerate(a):
    d[j] = i

uf = [-1]*n
def root(a):
    if uf[a] < 0:
        return a
    uf[a] = root(uf[a])
    return uf[a]
def unite(a,b):
    ra,rb = root(a),root(b)
    if ra==rb:
        return False
    if uf[ra] > uf[rb]:
        ra,rb = rb,ra
    uf[ra] += uf[rb]
    uf[rb] = ra
    return True

ans = 0
for i in range(n,0,-1):
    left=right=0
    ind = d[i]

    if ind<n-1 and a[ind] < a[ind+1]:
        right -= uf[root(ind+1)]
        unite(ind, ind+1)
    if ind>0 and a[ind] < a[ind-1]:
        left -= uf[root(ind-1)]
        unite(ind, ind-1)
    ans += i*(left+1)*(right+1)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(map(int,input().split()))
p,q,r,d=[0]*(n+1),[i for i in range(n+2)],[i for i in range(n+2)],0
for i in range(n):
    p[s[i]]=i
for i in range(n,0,-1):
    h=p[i]
    x,y=q[h],r[h]
    d+=i*(h-x+1)*(y-h+1)
    q[y+1],r[x-1]=x,y
print(d)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = [0] * (N + 1)
for i in range(N):
    b[a[i]] = i + 1
l = [i for i in range(N + 2)]
r = [i for i in range(N + 2)]
ans = 0
for i in range(N, 0, -1):
    m = b[i]
    x = l[m]
    y = r[m]
    ans += (m - x + 1) * (y - m + 1) * i
    r[x - 1] = y
    l[y + 1] = x
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n

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

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

        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.size[y] += self.size[x]
            else:
                self.par[y] = x
                self.size[x] += self.size[y]

            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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


N = int(input())
a = [-1] + [int(_) for _ in input().split()] + [-1]
uf = UnionFind(N+1)
place = [-1]*(N+1)
ans = 0

for i in range(1, N+1):
    place[a[i]] = i

for i in range(N, 0, -1):
    left = right = 0
    if a[place[i]] < a[place[i]-1]:
        left = uf.tree_size(uf.find(a[place[i]-1]))
        uf.unite(a[place[i]], a[place[i]-1])
    
    if a[place[i]] < a[place[i]+1]:
        right = uf.tree_size(uf.find(a[place[i]+1]))
        uf.unite(a[place[i]], a[place[i]+1])
    
    ans += (left+1)*(right+1)*a[place[i]]

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    x = S()
    s = 0
    ans = len(x)
    for i in x:
        if i == "S":
            s += 1
        else:
            if s > 0:
                s -= 1
                ans -= 2
    print(ans)
    return

#B
def B():
    n = I()
    a = LI()
    f = [0 for i in range(n+1)]
    for i in range(n):
        f[a[i]] = i
    l = [i for i in range(n+1)]
    r = [i for i in range(n+1)]
    ans = 0
    for i in range(1,n+1)[::-1]:
        j = f[i]
        ans += (j-l[j]+1)*(r[j]-j+1)*i
        l[r[j]+1] = l[j]
        r[l[j]-1] = r[j]
    print(ans)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

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

l = []
r = []
s = []

for i, x in enumerate(a):
    left = i
    while len(s) > 0  and x < s[-1][0]:
        left = s[-1][1]
        s.pop()
        
    l.append(left)    
    s.append([x, left])

s = []
for i in range(n-1, -1, -1):
    right = i
    x = a[i]
    while len(s) > 0  and x < s[-1][0]:
        right = s[-1][1]
        s.pop()
        
    r.append(right)    
    s.append([x, right])
r = r[::-1]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A):
        idxs[a] = i
    ll = list(range(N + 1))
    rr = list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        idx = idxs[a]
        l, r = ll[idx], rr[idx]
        ans += (idx - l + 1) * (r - idx + 1) * a
        ll[r + 1] = l
        rr[l - 1] = r

    return ans

print(main())

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

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

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

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

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


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

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

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

print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [0]*(n+1)
l = [i for i in range(n+2)]
r = [i for i in range(n+2)]
ans = 0
for i in range(n): b[a[i]]=i
for i in range(n,0,-1):
	m = b[i]
	x,y = l[m],r[m]
	ans+=i*(m-x+1)*(y-m+1)
	l[y+1],r[x-1] = x,y
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

# 数字から要素の場所を求められるようにdictで管理しておく
d = {}
for i, ai in enumerate(a):
    d[ai] = i

h = []

# right[i]: i<jで、a[i]>a[j]となる最も小さいjを格納する。
right = [n-1] * n

# heapqはmin-heapなので、大きい順に取り出したい時はマイナスをつけて追加して、取り出すときに要素にマイナスをつけ直す。
for i in range(n):
    while h and -h[0] > a[i]:
        v = -heapq.heappop(h)
        right[d[v]] = i - 1
    heapq.heappush(h, -a[i])

h = []
left = [0] * n

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

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

print(ans)

Submission status: Accepted

Solution code:
import heapq


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

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


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

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

h = []
left = [0] * n

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

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

print(ans)

Submission status: Accepted

Solution code:
#木の根を求める
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

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

par = [0]*n #親
for i in range(n):
    par[i] = i
rank = [1]*n #深さ
size = [1]*n #size[i]:iを根とするグループのサイズ

b = [0]*(n+1) #b[i]:iがaにおいて何番目か
for i in range(n):
    b[a[i]]=i

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

print(ans)

Submission status: Accepted

Solution code:
#木の根を求める
def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)

#xとyの属する集合の併合
def unite(x,y,par,rank,size):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)

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

par = [0]*n #親
for i in range(n):
    par[i] = i
rank = [1]*n #深さ
size = [1]*n #size[i]:iを根とするグループのサイズ

b = [0]*(n+1) #b[i]:iがaにおいて何番目か
for i in range(n):
    b[a[i]]=i

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b,l,r,ans = [0]*(n+1),[i for i in range(n+2)],[i for i in range(n+2)],0
for i in range(n): b[a[i]]=i
for i in range(n,0,-1):
	m = b[i]
	x,y = l[m],r[m]
	ans+=i*(m-x+1)*(y-m+1)
	l[y+1],r[x-1] = x,y
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]
left = list(range(N + 2))
right = list(range(N + 2))
index = {A[i - 1]: i for i in range(1, N + 1)}
ans = 0
for a in range(N, 0, -1):
    i = index[a]
    l = left[i]
    r = right[i]
    ans += a * (i - l + 1) * (r - i + 1)
    left[r + 1] = l
    right[l - 1] = r
print(ans)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
N = int(input())
a = inpl()
b = {a[i]: i for i in range(N)}

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def getNums(As):
    nums = [0] * N
    stack = [(-1, 0)]
    for iA, A in enumerate(As):
        while stack[-1][1] > A:
            stack.pop()
        nums[iA] = iA - stack[-1][0]
        stack.append((iA, A))

    return nums


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

numLs = getNums(As)
numRs = getNums(reversed(As))
print(sum([A * numL * numR for A, numL, numR in zip(As, numLs, reversed(numRs))]))

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))

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

ans = 0
iLs = list(range(N + 1))
iRs = list(range(N + 1))
for A in reversed(range(1, N + 1)):
    iA = iAs[A]
    iL, iR = iLs[iA], iRs[iA]
    ans += A * (iA - iL + 1) * (iR - iA + 1)
    iLs[iR + 1] = iL
    iRs[iL - 1] = iR

print(ans)

Submission status: Accepted

Solution code:
class BIT_index:
    def __init__(self, n):
        self.BIT_prev = [n] * (n + 1)
        self.BIT_next = [n] * (n + 1)
        self.n = n

    def __addElement(self, BIT, idx):
        value = idx
        idx += 1
        while idx > 0:
            BIT[idx] = min(BIT[idx], value)
            idx -= idx & -idx

    def addElement(self, idx):
        self.__addElement(self.BIT_prev, self.n - 1 - idx)
        self.__addElement(self.BIT_next, idx)

    def __getIndex(self, BIT, idx):
        idx += 1
        ans = self.n
        while idx <= self.n:
            ans = min(ans, BIT[idx])
            idx += idx & -idx
        return ans

    def getIndexPrev(self, idx):
        return self.__getIndex(self.BIT_prev, self.n - 1 - idx)

    def getIndexNext(self, idx):
        return self.__getIndex(self.BIT_next, idx)


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

Bs = [i for A, i in sorted([(As[i], i) for i in range(N)])]

BIT = BIT_index(N)
ans = 0
for i, B in enumerate(Bs):
    iN = BIT.getIndexNext(B)
    iP = BIT.getIndexPrev(B)
    BIT.addElement(B)
    ans += (i + 1) * (iN - B) * (B - (N - 1 - iP))

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=[0]+[int(i) for i in input().split()]
par=[0 for i in range(N+1)]
size=[0 for i in range(N+1)]
def find(x):
    if (par[x]==x):
        return x
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    res=size[x]*size[y]
    size[x]+=size[y]
    par[y]=x
    return res
for i in range(N+1):
    par[i]=i
    size[i]=1
b=[0 for i in range(N+1)]
for i in range(N+1):
    b[a[i]]=i
ans=0
for j in range(1,N+1)[::-1]:
    i=b[j]
    ans+=a[i]
    if i-1>=1 and a[i-1]>a[i]:
        ans+=unite(i-1,i)*a[i]
    if i+1<=N and a[i+1]>a[i]:
        ans += unite(i+1,i)*a[i]
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b,l,r,ans = [0]*(n+1),[i for i in range(n+2)],[i for i in range(n+2)],0
for i in range(n): b[a[i]]=i
for i in range(n,0,-1):
	m = b[i]
	x,y = l[m],r[m]
	ans+=i*(m-x+1)*(y-m+1)
	l[y+1],r[x-1] = x,y
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
idx = {v: i for i, v in enumerate(A)}

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())

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

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

print(ans)

Submission status: Accepted

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

def f(l):
    p=[0]*(n+1)
    s=[(-1,0)] #sentinel
    for i,a in enumerate(l):
        while s[-1][1]>a: #delete items if larger than target
            s.pop()
        t=i-s[-1][0] #get distance(left--target)
        p[a]=t #P[x] means distance(left--x) its min equals to x
        s.extend([(i,a)]) #add items
    return p
p=f(l) #distance list (left--target)
q=f(l[::-1]) #distance list (target--right)
print(sum(i*p[i]*q[i] for i in l))

Submission status: Accepted

Solution code:
# 入力
import sys
stdin = sys.stdin

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

n = ni()
a = li()

# 各数のindexを格納
dic = {}
for i, ai in enumerate(a):
    dic[ai] = i
    
# 各indexに対して、左端のindexをleft, 右端のindexをrightに格納する
left = list(range(n+2))
right = list(range(n+2))

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

B = [0] * (n+1)

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect

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

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

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

B = [0] * (n+1)

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

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

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

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

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

print(ans)

Submission status: Accepted

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

order = [0]*(N+1)

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

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

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

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N = int(input())
a = list(map(int, input().split()))

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

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

print(ans)