Problem:
 Score : 700 points    Problem Statement Snuke loves constructing integer sequences.  There are N piles of stones, numbered 1 through N .
The pile numbered i consists of a_i stones.  Snuke will construct an integer sequence s of length Σa_i , as follows:   Among the piles with the largest number of stones remaining, let x be the index of the pile with the smallest index. Append x to the end of s .  Select a pile with one or more stones remaining, and remove a stone from that pile.  If there is a pile with one or more stones remaining, go back to step 1. Otherwise, terminate the process.   We are interested in the lexicographically smallest sequence that can be constructed. For each of the integers 1,2,3,...,N , how many times does it occur in the lexicographically smallest sequence?      Constraints  1 ≤ N ≤ 10^{5}  1 ≤ a_i ≤ 10^{9}         Input The input is given from Standard Input in the following format:  N  a_1  a_2  ...  a_{N}       Output Print N lines. The i -th line should contain the number of the occurrences of the integer i in the lexicographically smallest sequence that can be constructed.        Sample Input 1 2
1 2      Sample Output 1 2
1  The lexicographically smallest sequence is constructed as follows:   Since the pile with the largest number of stones remaining is pile 2 , append 2 to the end of s . Then, remove a stone from pile 2 .  Since the piles with the largest number of stones remaining are pile 1 and 2 , append 1 to the end of s (we take the smallest index). Then, remove a stone from pile 2 .  Since the pile with the largest number of stones remaining is pile 1 , append 1 to the end of s . Then, remove a stone from pile 1 .   The resulting sequence is (2,1,1) . In this sequence, 1 occurs twice, and 2 occurs once.       Sample Input 2 10
1 2 1 3 2 4 2 5 8 1      Sample Output 2 10
7
0
4
0
3
0
2
3
0

Solution (Python):


import sys
from collections import Counter

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(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = Counter(A)

unique = sorted(set(A), reverse=1) + [0]

D = {}
for i in range(N-1, -1, -1):
    D[A[i]] = i

ans = [0] * N
prevcnt = 0
mnidx = INF
for i, a in enumerate(unique[:-1]):
    nxta = unique[i+1]
    
    cnt = (a - nxta) * (C[a] + prevcnt)
    
    mnidx = min(mnidx, D[a])
    ans[mnidx] += cnt
    
    prevcnt += C[a]
[print(a) for a in ans]

Solution (Python):

"""

石の数が最大の内数字が大きいものから取り除いていくのが最適？

前にあるできるだけ数が多いものに譲っていく

優先度付きキューでaが大きい方からpopしていく？

numが現在より小さい→以降する
そうでない = 現在のnumよりは低いが次のnumよりは大きい
→次のnumが確定した瞬間に差分を計算して定常減少用に入れる

最後は残りを全部1に入れて終わり
"""
import heapq

N = int(input())

ans = [0] * N

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

q = []

for i,na in enumerate(a):

    heapq.heappush(q,[-1 * na , i])

nowa , nowi = heapq.heappop(q)
nowa *= -1
always = 0
tempq = [nowa]

for i in range(N-1):

    nexa , nexi = heapq.heappop(q)
    nexa *= -1

    if nexi > nowi:
        tempq.append(nexa)

    else:
        nowpl = always * (nowa - nexa)

        for j in tempq:
            nowpl += j - nexa

        always += len(tempq)
        tempq = [nexa]

        ans[nowi] += nowpl

        nowa = nexa
        nowi = nexi

ans[0] = sum(a) - sum(ans)

print ("\n".join(map(str,ans)))

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

num=A[0]
data=[[A[0],0]]

for i in range(1,N):
    if A[i]>num:
        data.append([A[i],i])
        num=A[i]
        
B=sorted(A,reverse=True)
C=[0]*N
C[0]=B[0]
for i in range(1,N):
    C[i]=C[i-1]+B[i]
    
    
ans=[0]*N
cnt=0
kkk=0
for i in range(len(data)-1,0,-1):
    
    zzz=data[i-1][0]
    while kkk<N and B[kkk]>zzz:
        kkk+=1
    num=C[kkk-1]-kkk*zzz
    num-=cnt
    ans[data[i][1]]=num
    cnt+=num

ans[0]=sum(A)-sum(ans)

for u in ans:
    print(u)

Solution (Python):




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

cnt = {}

for i in range(n):
    if a[i] in cnt:
        cnt[a[i]][0] = min(cnt[a[i]][0],i)
        cnt[a[i]][1]+=1
    else:
        cnt[a[i]] = [i,1]


mins = [[k,cnt[k][0],cnt[k][1]] for k in cnt]
mins.append([0,0,0])

mins.sort(reverse = True)

ans = [0]*n

for i in range(len(mins)-1):
    k,cntk,l = mins[i][0],mins[i][1],mins[i][2]
    ans[cntk] += (k-mins[i+1][0])*l
    mins[i+1][2]+=l
    if mins[i+1][1]>mins[i][1]:
        mins[i+1][1] = mins[i][1]


for ai in ans:
    print(ai)

Solution (Python):




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

cnt = {}

for i in range(n):
    if a[i] in cnt:
        cnt[a[i]][0] = min(cnt[a[i]][0],i)
        cnt[a[i]][1]+=1
    else:
        cnt[a[i]] = [i,1]


mins = [[k,cnt[k][0],cnt[k][1]] for k in cnt]
mins.append([0,0,0])

mins.sort(reverse = True)

ans = [0]*n

for i in range(len(mins)-1):
    k,cntk,l = mins[i][0],mins[i][1],mins[i][2]
    ans[cntk] += (k-mins[i+1][0])*l
    mins[i+1][2]+=l
    if mins[i+1][1]>mins[i][1]:
        mins[i+1][1] = mins[i][1]


for ai in ans:
    print(ai)

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
d = dd(int)
c = dd(int)
for i in range(N - 1, -1, -1):
  d[a[i]] = i
  c[a[i]] += 1
c[0] = 0
ks = sorted(d.keys())
res = [0] * N
for i in range(len(ks) - 1, 0, -1):
  x = ks[i]
  y = ks[i - 1]
  c[y] += c[x]
  d[y] = min(d[y], d[x])
for i in range(len(ks)):
  x = ks[i]
  y = 0
  if i > 0: y = ks[i - 1]
  res[d[x]] += c[x] * (x - y)
for r in res: print(r)

Solution (Python):
from bisect import bisect_right, bisect_left
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = inpl()
x = [-1]
y = [0]
for i in range(N):
    if A[i] > y[-1]:
        x.append(i)
        y.append(A[i])
ans = [0] * N
L = len(x)
k = [0] * (L+1)
i = N-1
base = y[-1]
for n in range(L-1,0,-1):
    roof = base
    base = y[n-1]
    height = roof - base
    k[n] += k[n+1]
    ans[x[n]] += k[n] * height
    while i >= x[n]:
        p = bisect_left(y, A[i])
        ans[x[p]] += A[i] - y[p-1]
        k[p-1] += 1
        i -= 1
for i in range(N):
    print(ans[i])

Solution (Python):
import collections
import heapq
n=int(input())
A=[int(i) for i in input().split()]
Ans=[0]*n
M=[0]
for i in range(n):
  M.append(max(M[-1],A[i]))
D=collections.defaultdict(int)
H=[]
for i in range(n):
  j=n-1-i
  if A[j]<=M[j]:
    heapq.heappush(H,-A[j])
  else:
    Ans[j]=(A[j]-M[j])*(D[A[j]]+1)
    D[M[j]]+=D[A[j]]+1
    ct=0
    while H:
      a=heapq.heappop(H)
      a=-a
      if a<=M[j]:
        heapq.heappush(H,-a)
        break
      else:
        Ans[j]+=a-M[j]
        D[M[j]]+=1

for a in Ans:
  print(a)

Solution (Python):
import collections
import heapq
n=int(input())
A=[int(i) for i in input().split()]
Ans=[0]*n
M=[0]
for i in range(n):
  M.append(max(M[-1],A[i]))
D=collections.defaultdict(int)
H=[]
for i in range(n):
  j=n-1-i
  if A[j]<=M[j]:
    heapq.heappush(H,-A[j])
  else:
    Ans[j]=(A[j]-M[j])*(D[A[j]]+1)
    D[M[j]]+=D[A[j]]+1
    ct=0
    while H:
      a=heapq.heappop(H)
      a=-a
      if a<=M[j]:
        heapq.heappush(H,-a)
        break
      else:
        Ans[j]+=a-M[j]
        D[M[j]]+=1

for a in Ans:
  print(a)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
b = list(range(n))
s = list(map(list,zip(a,b)))
s.sort(reverse=True)
s.append([0,0])
ans = [0]*n
for i in range(n):
  dif = s[i][0]-s[i+1][0]
  ans[s[i][1]] += dif*(i+1)
  if s[i+1][1]>s[i][1]:
    s[i+1][1] = s[i][1]
print(*ans,sep="\n")

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
l = [(x,i) for i,x in enumerate(a)]
l.sort(reverse=True)
l += [(0,n)]
g = [0]*n
m = n
for i in range(n):
  s = l[i][1]
  if m > s: m = s
  g[m] += (l[i][0]-l[i+1][0])*(i+1)
for x in g: print(x)

Solution (Python):
def examC():
    N, M = LI()
    if N-M//2>=0:
        ans = M//2
    else:
        ans = N + (M-N*2)//4
    print(ans)
    return

def examD():
    N = I()
    S = SI()
    for i1,i2 in [[0,0],[0,1],[1,0],[1,1]]:
        flag = True
        sheep = [1]*N
        sheep[0] = i1
        sheep[1] = i2
        for j in range(1,N-1):
            if S[j]=="o":
                cur = 1
            else:
                cur = 0
            sheep[j+1] = (sheep[j]^cur)^sheep[j-1]
        if S[-1] == "o":
            cur = 1
        else:
            cur = 0
        if sheep[0]!=(sheep[-1] ^ cur) ^ sheep[-2]:
            flag = False
        if S[0] == "o":
            cur = 1
        else:
            cur = 0
        if sheep[1]!=(sheep[0] ^ cur) ^ sheep[-1]:
            flag = False
        if flag:
            ans = ""
            for i in sheep:
                if i==1:
                    ans += "S"
                else:
                    ans += "W"
            print(ans)
            return
    print(-1)
    return

def examE():
    N = I()
    A = LI()
    Ai = [[0,0]]
    for i in range(N):
        Ai.append([A[i],i])
    Ai = sorted(Ai, key=lambda x:x[1], reverse = True)
    Ai = sorted(Ai, key=lambda x:x[0], reverse = True)

    ans = [0]*N
    now = N
    for i in range(N):
        now = min(now,Ai[i][1])
        ans[now] += (i+1)*(Ai[i][0]-Ai[i+1][0])
    for v in ans:
        print(v)
    return

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

import sys,copy,bisect,itertools,heapq,math
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
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

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

from collections import defaultdict
G = defaultdict(list)
D = {}

for i in range(N):
    tmp = A[i]
    G[tmp].append(i)
    
keylist = []

for key in G:
    G[key].sort()
    D[key] = len(G[key])
    keylist.append(key)

keylist.sort()
keylist = keylist[::-1]
keylist.append(0)

D[0] = 0
G[0].append(0)

ans = [0]*N

for i in range(len(keylist)-1):
    key = keylist[i]
    nextkey = keylist[i+1]
    tmpi = G[key][0]
    ans[tmpi] += D[key]*(key-nextkey)
    
    D[nextkey] += D[key]
    G[nextkey][0] = min(G[nextkey][0],tmpi)
    
for i in ans:
    print(i)

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]

S = sum(A)
for i in range(N):
    A[i] = [A[i], i+1]

A.sort(reverse=True)
ans = [0]*(N+1)
i = 0
num = N+1
while i < N-1:
    num = min(num, A[i][1])
    while i < N-1 and A[i][0] == A[i+1][0]:
        num = min(num, A[i+1][1])
        i += 1
    if i == N-1:
        break
    ans[num] += (i+1)*(A[i][0]-A[i+1][0])
    i += 1

ans[1] += S-sum(ans)
for i in range(1, N+1):
    print(ans[i])

Solution (Python):
from bisect import bisect_left, bisect_right

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

Bs = [0]
xs = [-1]
for i, A in enumerate(As):
    if Bs[-1] < A:
        Bs.append(A)
        xs.append(i)

lenB = len(Bs)
sumAs = [0] * lenB
numFulls = [0] * lenB
for A in As:
    i = bisect_left(Bs, A)
    sumAs[i] += A - Bs[i-1]
    numFulls[i-1] += 1

for i in reversed(range(lenB-1)):
    numFulls[i] += numFulls[i+1]

anss = [0] * N
for i in range(1, lenB):
    ans = sumAs[i]
    ans += (Bs[i]-Bs[i-1]) * numFulls[i]
    anss[xs[i]] = ans

print('\n'.join(map(str, anss)))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
l = []
ans = [0 for i in range(n)]
for i in range(n):
    l.append([a[i],i])
l.sort(key=lambda x:x[1],reverse=True)
l.sort(key=lambda x:x[0],reverse=True)
count = 1
count0 = 0
b = l[0][0]
c = l[0][1]
for i in range(1,n):
    if l[i][0] == b:
        count += 1
        c = min(c,l[i][1])
    else:
        ans[c] += (b-l[i][0])*count
        count += 1
        b = l[i][0]
        c = min(l[i][1],c)
ans[c] += b*count
for i in range(n):
    print(ans[i])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    AI=[(a,i) for i,a in enumerate(map(int,input().split()))]
    AI.append((0,-1))
    AI.sort(reverse=1)

    m=INF
    ans=[0]*n
    for i in range(n):
        d=AI[i][0]-AI[i+1][0]
        m=min(m,AI[i][1])
        ans[m]+=(i+1)*d

    print(*ans,sep='\n')
resolve()

Solution (Python):
def main():
    n=int(input())
    a=list(map(int,input().split()))
    d={0:[-1]}
    for j,i in enumerate(a):
        if i in d.keys():d[i].append(j)
        else:d[i]=[j]
    d=sorted([[i,min(j),len(j)] for i,j in d.items()],reverse=True)
    ans=[0]*n
    l=0
    m=n
    for k in range(len(d)-1):
        x,y,z=d[k]
        l+=z
        m=min(m,y)
        ans[m]+=(x-d[k+1][0])*l
    for i in ans:
        print(i)
main()

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
D = []
for id,a in enumerate(A):
  D.append([a,id])
D = sorted(D)[::-1]
D.append([0,0])





cnt = [0] * N
minid = D[0][1]
for i in range(N):
  d = D[i][0] - D[i+1][0]
  cnt[minid] += d * (i + 1)
  if D[i+1][1] < minid:
    minid = D[i+1][1]
for i in range(N):
  print(cnt[i])

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

a = list(zip(a, range(len(a))))
a = sorted(a, reverse = True) + [(0, 0)]

ans = [0] * n
min_ind = 10**9

for i in range(n):
    tmp = a[i][0] - a[i+1][0]
    min_ind = min(min_ind, a[i][1])
    ans[min_ind] += (i+1) * tmp

for i in ans:
    print(i)

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left

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

dics = []
q = []
Ind = []
ans = [0]*N

for i, a in enumerate(A):
    ia = bisect_left(q, a)
    if ia == len(q):
        Ind.append(i)
        q.append(a)
        dics.append({a:1})
    else:
        dic = dics[ia]
        if not a in dic.keys():
            dic[a] = 1
        else:
            dic[a] += 1

L = len(q)
for l in reversed(range(L)):
    if l == 0:
        for k, v in dics[0].items():
            ans[Ind[0]] += k*v
    else:
        bef = q[l-1]
        for k, v in dics[l].items():
            ans[Ind[l]] += (k-bef)*v
            dics[l-1][bef] += v

for a in ans:
    print(a)

Solution (Python):
from collections import defaultdict

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

b = defaultdict(lambda : [float('inf'), 0])
for i in range(N) :
    b[a[i]][0] = min(b[a[i]][0], i)
    b[a[i]][1] += 1


c = [(0, 0, 0)]
for k, v in b.items() :
    c.append((k, v[0], v[1]))
c.sort()

ret = [0] * N
pre_v, pre_i, pre_c = c.pop()
while c :
    cur_v, cur_i, cur_c = c.pop()
    ret[pre_i] += (pre_v - cur_v) * pre_c
    cur_c += pre_c
    pre_v, pre_i, pre_c = cur_v, min(pre_i, cur_i), cur_c
    
for r in ret :
    print(r)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

def main():
    n = int(input())
    a = [(i, _a) for i, _a in enumerate(map(int, input().split()))]
    a.append((n, 0))
    ans = [0 for _ in range(n)]
    a = list(sorted(a, key=lambda x: (-x[1], x[0])))
    mini = a[0][0]
    for j, _a in enumerate(a):
        if j>0 and a[j-1][1] != _a[1]:
            ans[mini] += (a[j-1][1] - _a[1]) * j
            mini = min(mini, a[j][0])
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
e=enumerate
n,a=open(0)
a=sorted((int(i),j)for j,i in e(('0 '+a).split()))[::-1]
c=[0]*int(n)
t=10**18
for k,(i,j)in e(a[:-1],1):
  t=min(t,j)
  c[t-1]+=(i-a[k][0])*k
print(*c)

Solution (Python):
e=enumerate
n,a=open(0)
a=sorted((int(i),j)for j,i in e(('0 '+a).split()))[::-1]
c=[0]*int(n)
t=10**18
for k,(i,j)in e(a[:-1],1):
  t=min(t,j)
  c[t-1]+=(i-a[k][0])*k
print(*c)

Solution (Python):
N = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()))]
A.sort(reverse=True)
A.append((0, 0))

ans = [0] * N
now = float('inf')

for j, (a, i) in enumerate(A[:N], start=1):
    now = min(now, i)
    ans[now] += j * (a - A[j][0])

print(*ans, sep='\n')

Solution (Python):

n = int(input())
a = [0] + list(map(int, input().split()))
p = sorted((-a[i], -i) for i in range(n + 1))
ans = [0] * (n + 1)
m = n
for i in range(n):
    k, v = -p[i][1], -p[i][0]
    nv = -p[i + 1][0]
    m = min(m, k)
    ans[m] += (i + 1) * (v - nv)
print(*ans[1:], sep='\n')

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n = int(input())
    a = list(map(int, input().split()))
    ai = [(0, 0)]
    for i, _a in enumerate(a):
        ai.append((_a, i+1))
    ai.sort(key=lambda x: (-x[0], x[1]))
    ans = [0 for _ in range(n)]
    mini = ai[0][1]
    for i in range(n):
        if mini > ai[i][1]:
            mini = ai[i][1]
        ans[mini-1] += (i+1) * (ai[i][0] - ai[i+1][0])
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys,bisect
    input = sys.stdin.readline

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

    b = [0] + sorted(a)

    res = [0]*n

    d = dict()
    for i in range(n):
        if not a[i] in d:
            d[a[i]] = i

    p = n
    while p > 0:
        k = bisect.bisect_left(b,b[p])
        res[d[b[k]]] += (n+1-k)*(b[k]-b[k-1])
        if k -1 >= 1:
            d[b[k-1]] = min(d[b[k]],d[b[k-1]])
        p = k-1
    for e in res:
        print(e)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

top_list = [0]


for i in range(1, N):

	if a[i] > a[top_list[-1]]:
		top_list.append(i)

num_list = [0]*N
com = []
for i in range(len(top_list)):
	com.append(a[top_list[i]])
com.sort()

for i in range(N - 1, top_list[-1], -1):
	com.append(a[i])
com.sort()

stock = 0

for top in range(len(top_list) - 2, -1, -1):
	if top_list[top + 1] - top_list[top] > 10000:
		for i in range(top_list[top + 1] - 1, top_list[top], -1):
			
			com.append(a[i])
		com.sort()
	else:
		for i in range(top_list[top + 1] - 1, top_list[top], -1):
			bisect.insort(com, a[i])

	judge = 0
	total = stock*(a[top_list[top + 1]] - a[top_list[top]])
	
	while judge == 0:
		x = com.pop()
		if x > a[top_list[top]]:
			total += x - a[top_list[top]]
			stock += 1
		else:
			bisect.insort(com, x)
			judge = 1
	num_list[top_list[top + 1]] = total
	


num_list[top_list[0]] = sum(a) - sum(num_list)
for i in range(N):
	print(num_list[i])

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




ans = [0] * N

numList = [(a, i) for i, a in enumerate(A)]
numList.sort(reverse=True)
numList.append((0, 0))

y = float('inf')
for c, (a, i) in enumerate(numList[: N], start=1):
    y = min(y, i)
    ans[y] += c * (a - numList[c][0])

print(*ans, sep='\n')

Solution (Python):
import bisect

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

big_list = []
num_list = []
biggest = 0
for i, a_i in enumerate(a):
    if a_i > biggest:
        big_list.append(a_i)
        num_list.append(i)
        biggest = a_i
big_list.append(10 ** 10)
big_list.append(0)
num_list.append(0)
num_list.append(0)

ans = [0] * N
a.sort()
j = 0
for i, a_i in enumerate(a):
    if a_i < big_list[j]:
        ans[num_list[j]] += a_i - big_list[j - 1]
    else:
        ans[num_list[j]] += (big_list[j] - big_list[j - 1]) * (N - i)
        j += 1
for i in range(N):
    print(ans[i])

Solution (Python):

n = int(input())
a = [int(item) for item in input().split()]
awid = []
for i, item in enumerate(a):
    awid.append((item, i))
awid.sort(reverse=True)

bit = [0] * (n + 1) 
cnt = [0] * (n + 1) 

def bit_add(bit, x, w):
    while x <= n:
        bit[x] += w
        x += x & -x


def bit_sum(bit, x):
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= x & -x
    return ret

min_as = [-1] * n
min_a = 0
for i, item in enumerate(a):
    if item > min_a:
        min_as[i] = min_a
        min_a = item

ans = [0] * n
itr = 0
subbed = 0
for i, item in enumerate(min_as[::-1]):
    place = n - 1 - i
    if item != -1:
        while itr < n and awid[itr][0] > item:
            val, index = awid[itr]
            bit_add(bit, index + 1, val)
            bit_add(cnt, index + 1, 1)
            itr += 1
        ret = bit_sum(bit, n) - bit_sum(bit, place) - (bit_sum(cnt, n) - bit_sum(cnt, place)) * item - subbed
        ans[place] = ret
        subbed += ret
for item in ans:
    print(item)

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
D = []
for i in range(N):
    D.append((a[i], i))
D.append((0, -1))
D.sort(reverse=True)
ans = [0] * N
mi = float('inf')
for i in range(N):
    mi = min(mi, D[i][1])
    ans[mi] += (D[i][0] - D[i + 1][0]) * (i + 1)

for i in ans:
    print(i)

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

XY = [(a, i) for i, a in enumerate(A)]
XY.sort(reverse=True)


ans = [0] * N
min_y = IINF
for i, (x, y) in enumerate(XY):
    min_y = min(min_y, y)
    x2 = XY[i + 1][0] if i + 1 < N else 0
    ans[min_y] += (x - x2) * (i + 1)
print(*ans, sep='\n')

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * 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

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
A = np.array(A, dtype=int)
ans = np.zeros(N, dtype=int)








counts = Counter(A)
counts[0] = 0
counts[IINF] = 0
keys = list(sorted(counts.keys()))

ki = 0
cnt = 0
s = 0
for i in range(N):
    if A[i] - s <= 0:
        continue
    m = A[i]
    
    p = s
    while keys[ki] <= m:
        ans[i] += (keys[ki] - p) * (N - cnt)
        p = keys[ki]
        cnt += counts[keys[ki]]
        ki += 1

    s = A[i]

print(*ans, sep='\n')

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

for i in range(n):
    a[i] = [a[i],i]

a.sort()
a.reverse()
a.append([0,-1])

b = [0]*n
c = float('inf')

for i in range(n):
    c = min(c,a[i][1])
    b[c] += (a[i][0]-a[i+1][0])*(i+1)

print('\n'.join(map(str,b)))

Solution (Python):
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]

n=I()
a=LI()

d={}
nd={}
for i,x in enumerate(a):
    if x in d:
        d[x]=min(i,d[x])
        nd[x]+=1
    else:
        d[x]=i
        nd[x]=1

A=sorted([i for i in d.items()],key=lambda x:x[0])
ans=[0]*n
px,pm=A.pop()
nn=nd[px]
while A:
    x,m=A.pop()
    ans[pm]+=(px-x)*nn
    nn+=nd[x]
    px,pm=x,min(m,pm)
ans[0]+=sum(a)-sum(ans)
for i in ans:
    print(i)

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
a=LI()

d={}
nd={}
for i,x in enumerate(a):
    if x in d:
        d[x]=min(i,d[x])
        nd[x]+=1
    else:
        d[x]=i
        nd[x]=1

A=[i for i in d.items()]
A=sorted(A,key=lambda x:x[0])

ans=[0]*n
px,pm=A.pop()
nn=nd[px]
while A:
    x,m=A.pop()
    ans[pm]+=(px-x)*nn
    nn+=nd[x]
    px,pm=x,min(m,pm)
ans[0]+=sum(a)-sum(ans)


for i in ans:print(i)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter

"""
・左から見て最大値
・自分より右に、自分より以上の数がいくつあるか
・自分の下の数が何か
"""

N = int(input())
A = [int(x) for x in input().split()]

nums = sorted(set(A), reverse = True)
nums.append(0)
answer = [0] * N
counter = Counter(A)
position = dict() 
for i,a in enumerate(A):
    if not (a in position):
        position[a] = i


for n, next_n in zip(nums[:-1], nums[1:]):
    i = position[n]
    c = counter[n]
    
    counter[n] -= c
    counter[next_n] += c
    if next_n != 0:
        position[next_n] = min(position[next_n], i)
    answer[i] += c * (n - next_n)

print('\n'.join(map(str,answer)))

Solution (Python):
from operator import itemgetter
import sys
N=int(input())
A=[int(i) for i in input().split()]
B=[(A[i],i) for i in range(N)]
B=sorted(B,key=itemgetter(1))
B=sorted(B,key=itemgetter(0))
T=[0]*N
cos,pt=B.pop()
for i in range(1,N):
    cos2,pt2=B.pop()
    T[pt]+=(cos-cos2)*i
    pt=min(pt,pt2)
    cos=cos2
T[pt]+=cos*N
for i in T:
    print(i)

Solution (Python):
from collections import defaultdict
import sys
class BIT():
    def __init__(self, number):
        self.n = number
        self.list = [0] * (number + 1)

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

    def search(self, i):  
        s = 0
        while i > 0:
            s += self.list[i]
            i -= i & -i
        return s

    def suma(self, i, j):  
        return self.search(j) - self.search(i - 1)

N=int(input())
A=[int(i) for i in input().split()]
C=sorted(set(A))
ndd=defaultdict(int)
for i in range(len(C)):
    ndd[i+1]=C[i]
dd=defaultdict(int)
for i in range(len(C)):
    dd[C[i]]=i+1

visit=[0]*N
visit[0]=1
s=A[0]
H=[]
H.append(s)
for i in range(1,N):
    if s<A[i]:
        s=A[i]
        H.append(s)
        visit[i]=1

BITI=BIT(N+1)
BITI2=BIT(N+1)
j=len(H)-1
l=dd[H[j]]
num=sum(A)
T=[0]*N
ans=0
for i in range(N-1,-1,-1):
    if l==dd[A[0]]:
        break
    BITI.add(dd[A[i]],A[i])
    BITI2.add(dd[A[i]],1)
    if dd[A[i]]==l and visit[i]==1:
        T[i]=BITI.suma(dd[H[j-1]],N+1)-BITI2.suma(dd[H[j-1]],N+1)*H[j-1]-ans
        ans+=T[i]
        
        j-=1
        l=dd[H[j]]
x=num-sum(T)
T[0]=x

for t in T:
    print(t)

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
b = []
for i in range(N):
    b.append([a[i], i+1])
b.sort(reverse = True)
ans = [0]*(N+1)
mini = N+1

for i in range(N-1):
    mini = min(mini, b[i][1])
    if b[i+1][0] - b[i][0] < 0:
        ans[mini] += (b[i][0] - b[i+1][0])*(i+1)

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = sorted(list(set(a)))
a_to_i = dict()
for i in range(len(b)):
	a_to_i[b[i]] = i

a_count = [0 for _ in range(len(b))]
for x in a:
	a_count[a_to_i[x]] += 1

cum_reversed = [a_count[-1]]
for i in range(len(b)-2, -1, -1):
	cum_reversed.append(cum_reversed[-1] + a_count[i])

dominant = [-1 for _ in range(len(b))]
i = 0
for j in range(n):
	if i == len(b):
		break
	while a[j] >= b[i]:
		dominant[i] = j
		i += 1
		if i == len(b):
			break
b.reverse()
b.append(0)
dominant.reverse()

ans = [0 for _ in range(n)]

for i in range(len(b)-1):
	ans[dominant[i]] += (b[i] - b[i+1]) * cum_reversed[i]

print(*ans, sep="\n")

Solution (Python):

import heapq


def solve(n, a):

    ans = [0] * n

    q = []
    for i in range(n):
        ai = a[i]
        heapq.heappush(q, (-ai, i))

    ap, p = heapq.heappop(q)
    ap = -ap
    c = 0
    cnt = 1
    while len(q):
        ai, i = heapq.heappop(q)
        ai = -ai
        if p < i:
            c -= ap - ai
            cnt += 1
        else:
            ans[p] = c + (ap - ai) * cnt
            cnt += 1
            p = i
            ap = ai
            c = 0

    ans[p] = c + ap * cnt

    for c in ans:
        print(c)


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

    solve(n, a)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
def inpl(): return list(map(int, input().split()))

N = int(input())
A = inpl()
X = sorted([(a, i) for i, a in enumerate(A, start=1)], key=lambda x: [x[0], -x[1]])
answer = [0]*(N+1)
a, i = X.pop()

for c in range(1, N):
    b, j = X.pop()
    answer[i] += (a-b)*c
    i = min(i, j)
    a = b
answer[i] += a * N

print(*answer[1:], sep="\n")

Solution (Python):
N=int(input())
A=[(int(a),i) for i,a in enumerate(input().split())]
A.append((0,float("inf")))
A.sort()
k=A[-1][1]
ans=[0]*N
for i in range(N)[::-1]:
  ans[k]+=(A[i+1][0]-A[i][0])*(N-i)
  k=min(k,A[i][1])
for i in range(N):
  print(ans[i])

Solution (Python):
import itertools, bisect
def inpl(): return [int(i) for i in input().split()]

N = int(input())
a = inpl()
sa = sorted(a)
acsa = list(itertools.accumulate(sa)) + [0]
acans = 0
ma = 0
ans = [0]*N
for i in range(N):
    if ma >= a[i]:
        continue
    ma = a[i]
    x = bisect.bisect_left(sa, a[i]) - 1
    ans[i] = a[i]*(N-1-x) + acsa[x] - acans
    acans += ans[i]
    
for i in ans:
    print(i)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
As = sorted(A)
cumax = [0]*N
ma = 0
for i, a in enumerate(A):
    cumax[i] = max(cumax[i-1], a)

ias = 0
pma = 0
ofs = 0
for i, a in enumerate(cumax):
    if a == pma:
        print(0)
        continue
    s = 0
    while ias < N and As[ias] <= a:
        s += As[ias] - ofs
        ias += 1
    s += (N-ias)*(a-ofs)
    pma = a
    ofs = a
    print(s)

Solution (Python):
import heapq
N = int(input())
A = list(map(int, input().split()))


A = sorted([(ai, i) for i, ai in enumerate(A, start=1)], reverse=True)


A.append((0, 0))


ans = [0] * (N + 1)
y = []
for i in range(N):
    heapq.heappush(y, A[i][1])
    ans[y[0]] += (i + 1) * (A[i][0] - A[i + 1][0])

print(*ans[1:], sep="\n")

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

ans = [0]*n

b = []

for i, x in enumerate(a):
    b.append([-x, i])

b.sort()

c = []
p = b[0]
x = [-b[0][0], b[0][1], 1]
for i in range(1, n):
    if -b[i][0] == x[0]:
        x[2] = i+1
    else:
        c.append(x)
        x = [-b[i][0], b[i][1], i+1]
c.append(x)

s = 0
t = c[0][1]
for i in range(len(c)-1):
    x = (c[i][0]-c[i+1][0])*c[i][2]
    t = min(t, c[i][1])
    ans[t] += x
    s += x
ans[min(t, c[-1][1])] += sum(a)-s

for x in ans:
    print(x)