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):
n = int(input())
a = list(map(int,input().split()))

ans = [0] * (n+1)
d = dict()
for i,ai in enumerate(a,1):
    if(ai in d):
        d[ai][1] += 1
    else:
        d[ai] = [i,1]
d[0] = [0,0]

a_unique = list(set(a))
a_unique.sort(reverse=True)
a_unique.append(0)

for i in range(len(a_unique)-1):
    num = a_unique[i]
    next = a_unique[i+1]
    head = d[num][0]
    ans[head] += (num-next) * d[num][1]

    d[next][0] = min(d[next][0],d[num][0])
    d[next][1] += d[num][1]

print('\n'.join(map(str,ans[1:])))

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

b = sorted([(i+1, a[i]) for i in range(n)], key=lambda x: -x[1])
ans = [0]*(n+1)
m = float('inf')
for i in range(n-1):
    m = min(m, b[i][0])
    if b[i][1] == b[i+1][1]:
        continue
    ans[m] += (i+1)*(b[i][1]-b[i+1][1])
ans[1] += sum(a) - sum(ans)
for i in range(1, n+1):
    print(ans[i])

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

L = list(range(1, N+1))

ZIP = zip(A, L)

ZIP = sorted(ZIP, reverse = True)

A, L = zip(*ZIP)

ans = [0] * (N + 1)

MIN = float('INF')

for i in range(N-1):
    MIN = min(MIN, L[i])
    if A[i] - A[i+1] == 0:
        continue
    ans[MIN] += (A[i] - A[i+1]) * (i + 1)
ans[1] += sum(A) - sum(ans)

for i in range(1, N+1):
    print(ans[i])

Solution (Python):
from sys import exit
from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
ans = [0 for _ in range(n)]
D = dict()
S = set(A)
if len(S) == 1:
    print(sum(A))
    for _ in range(n - 1):
        print(0)
    exit()
X = sorted(S, reverse=True)
for i, x in enumerate(X):
    D[x] = i

index = [n + 1 for _ in range(len(S))]
for i, a in enumerate(A):
    index[D[a]] = min(index[D[a]], i)

cnt = 0
x = n + 1

for i in range(1, len(S)):
    tmp = X[i - 1]
    nxt = X[i]
    cnt += C[tmp]
    x = min(x, index[D[tmp]])
    ans[x] += (tmp - nxt) * cnt

for i, a in enumerate(A):
    if a != 0:
        cnt += C[nxt]
        ans[i] += nxt * cnt
        break

for a in ans:
    print(a)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
b = [(a[i],i) for i in range(n)]
b.sort(reverse=True)
b.append((0,0))
ans = [0]*n
v = b[0][1]
for i in range(n):
    ans[v] += (i+1)*(b[i][0]-b[i+1][0])
    v = min(v,b[i+1][1])
for i in range(n):
    print(ans[i])

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

    a.sort(key=lambda x: x[1], reverse=True)
    a.append((-1, 0))

    
    min_ind = n
    ans = [0] * n
    for i in range(n):
        ind, value = a[i]
        if ind < min_ind:
            min_ind = ind

        ans[min_ind] += (value - a[i+1][1]) * (i+1)

    for i in ans:
        print(i)

main()

Solution (Python):
def main(n,a):
  ret=[0]*n
  d={}
  for i,x in enumerate(a):
    if x in d:
      d[x].append(i)
    else:
      d[x]=[i]
  v=sorted(list(d.keys()),reverse=True)
  cnt_idx=0
  min_idx=n+1
  for i,x in enumerate(v):
    cnt_idx+=len(d[x])
    min_idx=min(min_idx,d[x][0])
    nx=0
    if i<len(v)-1:nx=v[i+1]
    ret[min_idx]+=cnt_idx*(x-nx)
  return ret

n=int(input())
a=list(map(int,input().split()))
print(*main(n,a),sep='\n')

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    ans = [0]*n
    a = [int(i) for i in ipt().split()]
    cts = [(a[0],0)]
    d = defaultdict(int)
    d[a[0]] = 1
    tot = a[0]
    for i,ai in enumerate(a[1::]):
        tot += ai
        d[ai] += 1
        if cts[-1][0] < ai:
            cts.append((ai,i+1))


    nms = sorted(d.keys(),reverse=True)
    lc = len(cts)-1
    na = cts[lc][0]
    ps = cts[lc][1]
    sm = 0
    for i in nms:
        sm += d[i]
        if i == na:
            lc -= 1
            na = cts[lc][0]
            ans[ps] += sm*(i-na)
            pps = ps
            ps = cts[lc][1]
        else:
            ans[pps] += d[i]*(i-na)


    ans[0] = tot-sum(ans[1::])

    for i in ans:
        print(i)



    return None

if __name__ == '__main__':
    main()

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

sorted_iAs = sorted(map(tuple, enumerate(As)), key = lambda t: (t[1], t[0]), reverse = True)









ans = [0] * N
youngest_index = 10 ** 9
for index, (original_index, A) in enumerate(sorted_iAs):
    youngest_index = min(original_index, youngest_index)
    if index == N - 1:
        ans[youngest_index] += A * (index + 1)
    elif sorted_iAs[index + 1][1] < A:
        next_A = sorted_iAs[index + 1][1]
        ans[youngest_index] += (A - next_A) * (index + 1)

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

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
B=sorted([(i,a) for i,a in enumerate(A)],key=lambda x:x[1])[::-1]+[(N,0)]
d=[0]*N
m=N
for i in range(N):
    m=min(m,B[i][0])
    d[m]+=(i+1)*(B[i][1]-B[i+1][1])
print(*d,sep='\n')

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import accumulate
N = int(input())
A = list(map(int,input().split()))

inf = 10**10

S = [0] + sorted(list(set(A)))
dic = {s:inf for s in S}
cnt = {s:0 for s in S}
sm = {s:0 for s in S}
ml = [0]
for i, a in enumerate(A):
    if ml[-1] < a:
        ml.append(a)
    dic[a] = min(i,dic[a])
    cnt[a] += 1
    sm[a] += a

for ps, s in zip(S[:-1][::-1],S[::-1]):
    cnt[ps] += cnt[s]
    sm[ps] += sm[s]

ans = [0]*N
temp = {s:sm[s] - s*cnt[s] for s in S}

for ps, s in zip(ml[:-1][::-1],ml[::-1]):
    ans[dic[s]] = temp[ps] - temp[s]

[print(a) for a in ans]

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

res = [(0,-1)]+[(a[i],i) for i in range(n)]
res.sort()

ans = [0]*n
num = 0
cnt = 0
midx = idx = n-1
v = res[-1][0]


while res:
    
    ans[midx] += (v-res[-1][0])*cnt
    v = res[-1][0]

    while res and res[-1][0]==v:
        ai,idx = res.pop()        
        cnt += 1
    midx = min(midx,idx)

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

Solution (Python):
from collections import defaultdict

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

cnt = defaultdict(int)
pos = defaultdict(lambda :10**12)
ans = defaultdict(int)

for i, j in enumerate(a, start=1):
    pos[j] = min(pos[j], i)
    cnt[j] += 1

target = [list(i) for i in sorted(pos.items())][::-1]
size = len(target)

for i in range(len(target)-1):
    a, b = target[i]
    c, d = target[i+1]
    ans[b] += cnt[a]*(a-c)
    cnt[c] += cnt[a]
    cnt[a] = 0
    target[i+1][1] = min(target[i+1][1], b)

a = target[-1][0]
ans[1] += cnt[a]*a
for i in range(1, N+1):
    print(ans[i])

Solution (Python):

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
seq = []
freq = [0 for i in range(N+1)]
D = defaultdict(list)
minD = defaultdict(int)
for i, v in enumerate(A):
    D[v].append(i+1)
for key in D.keys():
    minD[key] = min(D[key])
for cnt in D.keys():
    seq.append((cnt, len(D[cnt]), minD[cnt]))
seq.append((0, 0, 0))
seq.sort(key=lambda x: -x[0])
now_height, now_size, now_min = seq[0]

for i in range(1, len(seq)):
    freq[now_min] += (now_height-seq[i][0]) * now_size
    now_min = min(now_min, seq[i][2])
    now_size += seq[i][1]
    now_height = seq[i][0]
for i in range(1, N+1):
    print(freq[i])

Solution (Python):

import sys
from bisect import bisect_left, bisect_right, insort

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

""" 
石数最大の中で右の山から取り除く
次の数までまとめて石を取り除く
"""
N = ir()
A = lr()
A = [(x, i+1) for i, x in enumerate(A)] + [(0, 0)]
A.sort(reverse=True)
answer = [0] * (N+1)  
mi = 10 ** 10
mi_index = 10 ** 10
for i, (x, pre_index) in enumerate(A[:-1]):
    diff = A[i][0] - A[i+1][0]
    if pre_index < mi_index:
        mi_index = pre_index
    answer[mi_index] += diff * (i+1)

print('\n'.join(map(str, answer[1:])))

Solution (Python):

import sys
from bisect import bisect_left, bisect_right, insort

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

""" 
左側で自分より小さい数字との差
右側で自分より大きい数字の数
石数最大の山で右の物から取り除く
"""
N = ir()
A = lr()
A = [(x, i+1) for i, x in enumerate(A)] + [(0, 0)]
A.sort(reverse=True)
answer = [0] * (N+1)  
mi = 10 ** 10
mi_index = 10 ** 10
for i, (x, j) in enumerate(A[:-1]):
    diff = A[i][0] - A[i+1][0]
    index = A[i][1]
    if index < mi_index:
        mi_index = index
    answer[mi_index] += diff * (i+1)

print('\n'.join(map(str, answer[1:])))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a = [(-num, i) for i,num in enumerate(a)]
a.append((0, -1))
import heapq
heapq.heapify(a)
ans = [0]*n

pnum, pi = heapq.heappop(a)
pnum *= -1
count = 1
v = pnum
while a:
    num, i = heapq.heappop(a)
    num *= -1
    if i<pi:
        ans[pi] = v - num*count
        v = num*(count+1)
        count += 1
        pi = i
    else:
        count += 1
        v += num
write("\n".join(map(str, ans)))

Solution (Python):
import sys
read = sys.stdin.read

n, *A = map(int, read().split())
S = sorted([(a, i) for i, a in enumerate(A)], reverse=True)
X, Y = zip(*S)
m = 10**9
L = [0]*n
for i, y in enumerate(Y):
  m = min(m, y)
  if i == n-1:
    L[m] += (i+1) * X[i]
  else:
    L[m] += (i+1) * (X[i] - X[i+1])
print(*L, sep="\n")

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = [[a[i], i] for i in range(n)]
b.sort(reverse = True)
d = {}
dcnt = {}
for i in range(n):
    if not a[i] in d:
        d[a[i]] = i
        dcnt[a[i]] = 1
    else:
        dcnt[a[i]] = dcnt[a[i]] + 1
b = [[0, 0] for _ in range(len(d) + 1)]
k = 0
for i, j in d.items():
    b[k][0], b[k][1] = i, j
    k += 1
b.sort(reverse = True)
ans = [0] * n
j = b[0][1]
cnt = 0
for i in range(len(d)):
    cnt += dcnt[b[i][0]]
    j = min(j, b[i][1])
    ans[j] += (b[i][0] - b[i + 1][0]) * cnt
for i in ans:
    print(i)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
import heapq
import sys

INF = 10 ** 17
MOD = 10 ** 9 + 7
def mint(lis):
    return list(map(int, lis))

def bifind(arr_sorted, x):
    idx = bisect_left(arr_sorted, x)
    if idx == len(arr_sorted):
        return False
    if arr_sorted[idx] == x:
        return True
    else:
        return False
def getyaku(n):
    ret = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            ret.append(i)
            ret.append(n // i)

    return ret

def find(x, a):
    idx = bisect_left(a, x)
    if idx == len(a):
        return False
    if a[idx] == x:
        return True
    else:
        return False

def main():
    n = getN()
    nums = getList()
    nums = [(x, i+1) for i, x in enumerate(nums)]
    nums.append((0, INF))
    nums.sort(key=lambda x: -x[0] * INF + x[1])
    
    mx = INF
    ans = [0 for i in range(n+1)]
    tmp_tgt = INF
    through = 0
    for a,b in nums:
        if a != mx:
            diff = mx - a



            if mx != INF:
                ans[tmp_tgt] += through * diff
            mx = a
            if b < tmp_tgt:
                tmp_tgt = b
        through += 1
    for an in ans[1:]:
        print(an)

if __name__ == "__main__":
    main()

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)
l = dd(lambda: N + 1)
for i in range(N):
  d[a[i]] += 1
  l[a[i]] = min(l[a[i]], i + 1)


ks = sorted(d.keys(), reverse = True)
res = [0] * (N + 1)
for i in range(len(ks) - 1):
  t = ks[i] - ks[i + 1]
  k = ks[i]
  res[l[k]] += d[k] * t
  d[ks[i + 1]] += d[k]
  l[ks[i + 1]] = min(l[ks[i + 1]], l[k])
res[1] += d[ks[-1]] * ks[-1]
for r in res[1: ]: print(r)

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

ans = [0]*N
num = 0
B = sorted(A)
j = 0
for i in range(N):
    cnt = 0
    while j < N and B[j] <= A[i]:
        cnt += max(0, B[j]-num)
        j += 1
    ans[i] = cnt + max(0, (N-j)*(A[i]-num))
    num = max(num, A[i])

for a in ans:
    print(a)

Solution (Python):
from bisect import bisect_right

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

li = [[0, -1]]
for i, e in enumerate(a):
    if e > li[-1][0]:
        li.append([e, i])

li = li[::-1]

a.sort()
acc = [0] * (n + 1)
for i in range(n - 1, -1, -1):
    acc[i] = acc[i+1] + a[i]

ans = [0] * n
sub = 0
ans_prev = 0
for (ep, ip), (e, i) in zip(li, li[1:]):
    j = bisect_right(a, e)
    ans[ip] = acc[j] - e * (n - j)

i_prev = 0
for i in range(1, n):
    if ans[i]:
        ans[i_prev] -= ans[i]
        i_prev = i

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

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

tmp = [[e, n - i] for i, e in enumerate(a)]
tmp.sort(reverse=True)

aa = [[e, n - i] for e, i in tmp] + [[0, -1]]

v_prev, i_prev = aa[0]
i = 0
ans = [0] * n
sm = 0
while i < n:
    while aa[i][1] >= i_prev:
        sm += aa[i][0]
        i += 1

    ans[i_prev] += sm - aa[i][0] * i
    sm = aa[i][0] * i
    v_prev, i_prev = aa[i]

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

Solution (Python):
from collections import defaultdict, Counter
N = int(input())
A = [0] + list(map(int, input().split()))
C = Counter(A)

value = sorted(set(A), reverse=True)
a_to_i = defaultdict(int)

for i, a in enumerate(A):
    if not a_to_i[a]:
        a_to_i[a] = i

ans = [0] * (N + 1)
cnt = 0
i = N
for x, y in zip(value[:-1], value[1:]):
    i = min(i, a_to_i[x])
    cnt += C[x]
    ans[i] += (x - y) * cnt

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

Solution (Python):
from collections import defaultdict
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = [0]*N
    min_inds = defaultdict(lambda: 10**5)
    nums = defaultdict(lambda: 0)
    for ind,a in enumerate(A):
        min_inds[a] = min(min_inds[a],ind)
        nums[a] += 1
    min_inds = sorted(list(map(list,min_inds.items())), key=lambda x:x[0])
    min_inds.append([10**9+1,10**5])
    nums = sorted(list(map(list,nums.items())), key=lambda x:x[0])
    nums.append([0,0])
    for i in range(len(min_inds)-2,-1,-1):
        min_inds[i][1] = min(min_inds[i][1],min_inds[i+1][1])
        nums[i][1] += nums[i+1][1]
        ans[min_inds[i][1]] += nums[i][1]*(nums[i][0]-nums[i-1][0])
    return ans
print(*solve(),sep='\n')

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

N = int(input())
a = list(map(int, input().split()))
aa = list(set(a))
aa.sort()
compress = {aa[i]: i for i in range(len(aa))}
cnt = [0] * len(aa)
idx = [-1] * len(aa)
for i in range(N)[::-1]:
    n = compress[a[i]]
    cnt[n] += 1
    idx[n] = i
ans = [0] * N
for n in range(1, len(aa))[::-1]:
    i = idx[n]
    ans[i] += cnt[n] * (aa[n] - aa[n-1])
    cnt[n-1] += cnt[n]
    idx[n-1] = min(idx[n-1], i)
ans[0] += N * aa[0]
print(*ans, sep='\n')

Solution (Python):
import bisect

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

inc=[[A[0],0]]
for i in range(1,N):
    if A[i]>inc[-1][0]:
        inc.append([A[i],i])

n=len(inc)
test=inc[:n-1]
query=[[] for i in range(n)]
for i in range(0,N):
    r=bisect.bisect_left(test,[A[i],i])
    query[r].append(A[i])

ans=[0 for i in range(N)]
count=0
for i in range(n-1,0,-1):
    fr=inc[i][0]
    to=inc[i-1][0]
    val=count*(fr-to)+sum(query[i])-to*len(query[i])
    ans[inc[i][1]]=val
    count+=len(query[i])

fr=inc[0][0]
to=0
val=count*(fr-to)+sum(query[0])-to*len(query[0])
ans[0]=val

for i in range(N):
    print(ans[i])

Solution (Python):
N = int(input())
A = [0] + list(map(int, input().split()))


B = [[a, i, 1] for i, a in enumerate(A)]
C = sorted(B, reverse=True)



a_max, idx = 0, 0 
left_max = [[0, 0] for i in range(N+1)] 
for i, a in enumerate(A):
  left_max[i] = [a_max, idx]
  if a > a_max:
    a_max, idx = a, i

ans = [0] * (N+1)
next_i = C[0][1]
for _, i, _ in C: 
  a, _, num = B[i] 
  if i == next_i:
    next_a, next_i = left_max[i] 
    now_i = i
    ans[i] += (a - next_a) * num 
    B[next_i][2] += num 
  else:
    ans[now_i] += (a - next_a) * num
    B[next_i][2] += num

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

Solution (Python):
N = int(input())
A = [0] + list(map(int, input().split()))
B = [[a, i, 1] for i, a in enumerate(A)]
C = sorted(B, reverse=True)
a_max, idx = 0, 0 
left_max = [[0, 0] for i in range(N+1)] 
for i, a in enumerate(A):
  left_max[i] = [a_max, idx]
  if a > a_max:
    a_max, idx = a, i

ans = [0] * (N+1)
next_i = C[0][1]
for _, i, _ in C:
  a, _, num = B[i]
  if i == next_i:
    next_a, next_i = left_max[i]
    now_i = i
    ans[i] += (a - next_a) * num
    B[next_i][2] += num
  else:
    ans[now_i] += (a - next_a) * num
    B[next_i][2] += num

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

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N = I()
a = LI()

asort = sorted(a)

d = defaultdict(int)
for i in range(N):
    d[a[i]] += 1
keys = sorted(list(d.keys()))

ans = [0]*N
max_ = 0
place = 0
for i in range(N):
    if a[i] > max_:
        diff = a[i]-max_
        num = N-bisect_left(asort,a[i])
        ans[i] = num*diff
        for j in range(place,len(keys)):
            if keys[j] <= max_:
                continue
            elif keys[j] >= a[i]:
                place = j
                break
            else:
                ans[i] += (keys[j]-max_)*d[keys[j]]
        max_ = a[i]

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

for i in range(N):
    print(ans[i])

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

parent = [(0,-1)]
now = 0
for i,a in enumerate(A):
    if now < a:
        parent.append((a,i))
        now = a
A.sort()
ans = [0]*n
cnt = 0
p = parent[-1][1]
for a in A[::-1]:
    if parent[-1][0] >= a:
        p = parent[-1][1]
        ans[p] += cnt*(parent[-1][0] - parent[-2][0])
        parent.pop()
    if parent[-1][0] < a:
        cnt += 1
        ans[p] += a - parent[-1][0]
print('\n'.join(str(i) for i in ans))

Solution (Python):
N = int(input())
B = list(map(int, input().split()))
A = [(B[i], i) for i in range(N)]

A.sort(key = lambda x: x[0], reverse = True)

A.append((0, 0))

ans = [0] * N
tmp = N + 1
count = 1
for index, a in enumerate(A[:-1]):
    tmp = min(tmp, a[1])
    ans[tmp] += count * (a[0] - A[index + 1][0])
    count += 1

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

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

from collections import defaultdict
d = defaultdict(lambda: (n, 0))
for i, a in enumerate(A):
    min_id, cnt = d[a]
    d[a] = (min(min_id, i), cnt+1)

B = list(d.items())
B.sort()



ans = [0]*n
while True:
    a1, (m1, c1) = B.pop()
    if not B:
        ans[m1] += c1*a1
        break
    a2, (m2, c2) = B[-1]
    ans[m1] += c1*(a1-a2)
    B[-1] = (a2, (min(m1, m2), c1+c2))

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

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

from collections import defaultdict
d = defaultdict(lambda: (n, 0))
for i, a in enumerate(A):
    min_id, cnt = d[a]
    d[a] = (min(min_id, i), cnt+1)

B = list(d.items())
B.sort()



ans = [0]*n
while True:
    a1, (m1, c1) = B.pop()
    if not B:
        ans[m1] += c1*a1
        break
    a2, (m2, c2) = B[-1]
    ans[m1] += c1*(a1-a2)
    B[-1] = (a2, (min(m1, m2), c1+c2))

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

Solution (Python):



def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [(a, i+1) for i, a in enumerate(A)]
    B.sort(reverse=True)
    B.append((0, 0))
    ans = [0]*(N+1)
    idx = N+1
    for i in range(N):
        add = (i+1)*(B[i][0] - B[i+1][0])
        idx = min(idx, B[i][1])
        ans[idx] += add
    print(*ans[1:], sep="\n")


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heapify, heappop

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

que = [(-a, i + 1) for i, a in enumerate(A)]
heapify(que)

ans = [0] * (N + 1)
cnt = 0
while que:
    a, now = heappop(que)
    cnt += 1
    ans[now] = -a * cnt

    while que and que[0][1] > now:
        a, _ = heappop(que)
        ans[now] += -a
        cnt += 1

    if que:
        ans[now] -= -que[0][0] * cnt

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

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
b=[[a[i],i] for i in range(n)]+[[0,n-1]]
b.sort(reverse=1)
ans=[0]*n
j=n-1
for i in range(n):
  j=min(b[i][1],j)
  c=b[i][0]-b[i+1][0]
  if c!=0:ans[j]+=c*(i+1)
print(*ans)

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

    target = [0]
    prev = a[0]
    for i in range(1, n):
        if a[i] > prev:
            target.append(i)
            prev = a[i]

    ax = [None] * n
    for i in range(n):
        ax[i] = [a[i], i]
    ax.sort(reverse=True)

    ans = [0] * n
    mult = 1
    for i in range(n-1):
        ans[target[-1]] += (ax[i][0] - ax[i+1][0]) * mult
        if (ax[i+1][0] < a[target[-1]] and ax[i+1][1] < target[-1]):
            target.pop()
        mult += 1
    ans[target[-1]] += ax[n-1][0] * mult

    for x in ans:
        print(x)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = [[int(i), j] for j, i in enumerate(input().split())]
a.sort(reverse=1)
a.append([0, n-1])
ans = [0] * n

j = n-1
for i in range(n):
    j = min(j, a[i][1])
    ans[j] += (i+1) * (a[i][0] - a[i + 1][0])
print("\n".join(map(str, ans)))

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    nDict = dict()
    Atype = list(set(A))
    Atype.sort(reverse = True)
    Atype.append(0)
    for i, a in enumerate(A):
        if a in nDict: nDict[a].append(i)
        else: nDict[a] = [i]
    count = [0] * N
    minIndex = N
    group = 0
    for i in range(len(Atype) - 1):
        cN = Atype[i]
        minIndex = min(minIndex, nDict[cN][0])
        group += len(nDict[cN])
        nextN = Atype[i + 1]
        count[minIndex] += (cN - nextN) * group
    print("\n".join(map(str, count)))

    return 0

if __name__ == "__main__":
    solve()

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
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
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()
L = LI()
A = [(L[i], i) for i in range(n)]
ans = [0] * n
A.sort()
min_ind = INF
for i in range(n - 1, 0, -1):
    min_ind = min(min_ind, A[i][1])
    if A[i - 1][0] < A[i][0]:
        ans[min_ind] += (A[i][0] - A[i - 1][0]) * (n - i)

ans[0] += A[0][0] * n
for j in ans:
    print(j)

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

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

for i in range(N-1, -1, -1):
    left[a[i]] = i

l = list(set(a))
l.sort(reverse=True)
ans = [0]*N
now = left[max(a)]
cnt = Counter(a)

for i in range(len(l)-1):
    ans[now] += (l[i]-l[i+1])*cnt[l[i]]
    cnt[l[i+1]] += cnt[l[i]]
    now = min(now, left[l[i+1]])

ans[now] += l[-1]*cnt[l[-1]]

for ans_i in ans:
    print(ans_i)

Solution (Python):
class BIT:
  def __init__(self, n):
    self.N = n+1
    self.bit = [0]*self.N
  
  def bit_sum(self, i):
    s = 0
    i += 1
    while i>0:
      s += self.bit[i]
      i -= i & -i
    return s

  def bit_add(self, i, n):
    i += 1
    while i<self.N:
      self.bit[i] += n
      i += i & -i

N, *A = map(int, open(0).read().split())
inf = [(a,i) for i, a in enumerate(A)]
n = A[0]
ls = [0]
for i in range(1,N):
  if A[i]>n:
    n = A[i]
    ls.append(i)
B = BIT(N)
C = BIT(N)
inf.sort(reverse=True)
cnt = [0]*N
ccnt = [0]*N
for a,i in inf:
  B.bit_add(i,a)
  cnt[i] = B.bit_sum(N-1)-B.bit_sum(i)
for a, i in inf:
  C.bit_add(i,1)
  ccnt[i] = C.bit_sum(N-1)-C.bit_sum(i)

ans = [0]*N
s = sum(A)
p = 0
x = 0
for i in range(len(ls)-1,0,-1):
  a = ls[i]
  b = ls[i-1]
  m = cnt[b]-A[b]*ccnt[b]
  n = m-x
  ans[a] = n
  s -= n
  x += ans[a]
ans[0] = s
print('\n'.join(map(str,ans)))

Solution (Python):
N = int(input())
L = [0] + list(map(int,input().split()))
D = {}
D[0] = [0,0]
for i in range(1,N+1):
    if L[i] not in D:
        D[L[i]] = [i,1]
    else:
        D[L[i]][1] += 1

A = list(D.items())
A.sort(reverse=True)


ans=0
ANS = [0 for i in range(N+1)]

for i in range(1,len(D)):
    ANS[A[i-1][1][0]] += (A[i-1][0] - A[i][0]) * A[i-1][1][1]
    A[i][1][0] = min(A[i-1][1][0],A[i][1][0])
    A[i][1][1] += A[i-1][1][1]

for i in range(1,len(ANS)):
    print(ANS[i])

Solution (Python):
def main():
    N,*A=map(int, open(0).read().split())
    L,C={},{}
    for i,a in enumerate(A):
        if a in C:
            C[a]+=1
        else:
            C[a]=1
            L[a]=i
    Z=[0]*N
    B=sorted(C,reverse=True)
    l=N-1
    cnt=0
    for b,c in zip(B,B[1:]+[0]):
        l=min(l,L[b])
        cnt+=C[b]
        Z[l]+=(b-c)*cnt
    print(*Z, sep="\n")

if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n = II()
    aa = LI()
    
    bot = []
    mx = 0
    for i, a in enumerate(aa):
        if a > mx:
            bot.append((mx, i))
            mx = a
    
    aa.sort()
    ans = [0] * n
    j = n
    s = 0
    fin=0
    for mx, i in bot[::-1]:
        while j > 0 and aa[j - 1] > mx:
            j -= 1
            s += aa[j]
        ans[i]=s-(n-j)*mx-fin
        
        fin+=ans[i]
    print(*ans,sep="\n")

main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ai = [(0, -1)] + [(a, i+1) for i, a in enumerate(A)]
    ai.sort()
    A = [a for a, i in ai]
    I = [i for a, i in ai]
    ans = [0] * (N+1)

    i = N
    same = 0
    q = []
    while i != 0:
        j = i
        while True:
            j -= 1
            if I[j] < I[i]:
                break
            heapq.heappush(q, A[j])
        d = A[i] - A[j]
        ans[I[i]] = d * (same+1)
        same += 1
        while q and q[0] >= A[j]:
            b = heapq.heappop(q)
            ans[I[i]] += b - A[j]
            same += 1
        i = j
    for r in ans[1:]:
        print(r)

def main():
    N = read_int()
    A = read_int_n()
    (slv(N, A))


if __name__ == '__main__':
    main()