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-----
2
1 2

-----Sample Output-----
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.

Difficulty: competition

Starter code:

Solutions:
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

# [value, first_appearance, count]
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)

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return list(map(int, input().split()))
def LI(): return list(map(int, input().split()))

"""
可能なら左から取る
左側にある数字のどれかに追い付いたら，そこはもう選ばれない．
選ぶ数字をどんどん左にシフトしていく．

左に移動するとき，左側にある最大値とその位置を取りたい:seg木でいける（A[i],-i）を持って最大値を取れば位置もわかる．

数字を使う回数をカウントするためには，左側にある最大値は必要．あと，右側にある自分と同じ数の個数，も必要．
個数だけでよく，位置情報はいらないので左にシフトしていくときにddで個数だけ持っておくか
右側の使い方が変だな，326154みたいな並びだと，6を3に下げるときに，右側にある45をどっちもを補足する必要あり

うわ，例2の答えのとこ見間違えてた，普通に計算した通りの転倒数ジャン．
i番目を見ている状態
次のものが自分より左側に出てくる:差分*i以上の位置にある個数
次のものが自分より右側に出てくる:むし

同じ数字が出てくるとき：次の数字は左側としたいが，右に出てくる分の個数も加味したい
+1ではなく，次の数との差分
とか思ってたけど，結局足すのは次に左の数が出てきた時なのでいらない

結局差分が大事．次との差分を見るだけならば，個数が同じグループのことをあまり考えなくても良い
大きい順に見ていくだけなので，個数=見た個数で良い


"""
def main():
    N=I()
    A=LI()
    for i in range(N):
        A[i]=(A[i],i)
    
    A.sort(reverse=True)
    A.append((0,0))
    ans=[0]*N
    
    now=A[0][1]#どこに追加するか
    for i in range(N):
        ans[now]+=(i+1)*(A[i][0] - A[i+1][0])
        now=min(now,A[i+1][1])
    
    for i in range(N):
        print((ans[i]))
    
    

main()


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

sx = []
c = 0
d = dict()
for x in sorted(list(set(X))):
    sx.append(x)
    d[x] = c
    c += 1
sx.append(10**18)

count = [0]*(c+1)
for x in X:
    count[d[x]] += 1
for i in range(c-1, -1, -1):
    count[i] += count[i+1]

count2 = [0]*(c+1)
for i in range(c-1, -1, -1):
    count2[i] = count[i+1]*(sx[i+1]-sx[i])
for i in range(c-1, -1, -1):
    count2[i] += count2[i+1]



Y = []
for i in range(N):
    Y.append((X[i], -i))
Y.sort()
R = []
while Y:
    y, j = Y.pop()
    j = -j
    if not R:
        R.append((d[y], j))
    else:
        if d[y] < R[-1][0] and j < R[-1][1]:
            R.append((d[y], j))



RR = [0]*N
b = 0
bi = 0
for y, i in R[:]:
    RR[bi] = count2[y]-b
    b = count2[y]
    bi = i
RR[0] = sum(X)-sum(RR[1:])
for r in RR:
    print(r)



n = int(input())
a = list(map(int, input().split()))
l = [(0, n)]
for i, A in enumerate(a):
    l.append((A, i))
l.sort(reverse=True)
ans = [0] * n
mi = float("inf")
for i in range(n):
    if mi > l[i][1]:
        mi = l[i][1]
    ans[mi] += (i + 1) * (l[i][0] - l[i + 1][0])
for i in range(n):
    print(ans[i])

from bisect import bisect_left

n = int(input())
alst = list(map(int, input().split()))
lst = list(set(alst))
lst.sort()
blst = []
for a in alst:
    blst.append(bisect_left(lst, a))

imos = [0 for _ in range(len(lst) + 10)]

for b in blst:
    imos[0] += 1
    imos[b + 1] -= 1
for i in range(1, len(lst) + 10):
    imos[i] += imos[i - 1]

bef = 0
for b in blst:
    if b < bef:
        print((0))
        continue
    total = 0
    while bef <= b:
        if bef == 0:
            total += imos[bef] * lst[bef]
        else:
            total += imos[bef] * (lst[bef] - lst[bef - 1])
        bef += 1
    print(total)


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)

from heapq import heappush, heappop
N = int(input())
A = [int(a) for a in input().split()]
S = {}
m = (1 << 18) - 1
for i, a in enumerate(A):
    if a not in S:
        S[a] = (i << 18) ^ 1
    else:
        aacc = S[a]
        aa, cc = aacc >> 18, aacc & m
        S[a] = (min(aa, i) << 18) ^ (cc + 1)

H = [0]
hpush = lambda x: heappush(H, -x)
hpop = lambda: -heappop(H)

for a in S:
    micc = S[a]
    mi, cc = micc >> 18, micc & m
    aicc = (a << 36) ^ (mi << 18) ^ cc
    hpush(aicc)

m36 = (1 << 36) - 1
m18 = (1 << 18) - 1
ANS = [0] * N
while len(H) > 1:
    aicc = hpop()
    a = aicc >> 36
    i = (aicc >> 18) & m18
    cc = aicc & m18
    aicc = hpop()
    a2 = aicc >> 36
    i2 = (aicc >> 18) & m18
    cc2 = aicc & m18
    ANS[i] += (a - a2) * cc
    
    if a2 == 0: continue
    hpush((a2 << 36) ^ (min(i, i2) << 18) ^ (cc + cc2))

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

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")

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()
    # できる数列にインデックスがかかれるときの最大値の底(bottom)
    bot = []
    mx = 0
    for i, a in enumerate(aa):
        if a > mx:
            bot.append((mx, i))
            mx = a
    #print(bot)
    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
        # print(mx,i,j,s,fin,ans)
        fin+=ans[i]
    print(*ans,sep="\n")

main()


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


def compress_coord(raw):
    v_i = {}
    for i, v in enumerate(raw):
        if v not in v_i:
            v_i[v] = []
        v_i[v] += [i]
    return v_i


a_i = compress_coord(A)
A2 = sorted(a_i.keys())[::-1]
ans = [0] * N
n = 0
i = 10**10
for iv, a in enumerate(A2):
    if iv < len(A2) - 1:
        anext = A2[iv + 1]
    else:
        anext = 0
    i = min(i, a_i[a][0])
    n += len(a_i[a])
    ans[i] += n * (a - anext)
print(*ans, sep='\n')


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()

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")

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")

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)))

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])

# frequency
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]
# howmany,group_size,minimum
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])

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')

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 = min(a[:i+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()

# coding: utf-8
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)  # 1-indexed
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:]))))


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)

# -*- coding: utf-8 -*-
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))


def __starting_point():
    main()

__starting_point()

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)

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)

def __starting_point():
    main()
__starting_point()

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')

# print (A)


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')

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])

#!/usr/bin/env python3
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')


#from collections import deque,defaultdict
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 # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

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])


#1は一意
#2は小さい番号の石の数が大きくなるように、大きい番号の石を除きたい

#個数が同順のものを、番号小以外が個数が時点になるまで除いてから、番号少を除く
n = int(input())
a = list(map(int, input().split( )))

cnt = {}#keyは個数、要素は最小番号

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)
#print(mins)
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]
#ans[mins[-1][1]]=n*mins[-1][0]

for ai in ans:
    print(ai)
    





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)

def __starting_point():
    main()

__starting_point()

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 # [value, idx]
left_max = [[0, 0] for i in range(N+1)] # [value, idx]
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')

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)
#print(A)

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])

3.6
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) 
# Add w to ax 
def bit_add(bit, x, w):
    while x <= n:
        bit[x] += w
        x += x & -x

# Sum a1 to ax 
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)

n=int(input())
a=tuple(map(int,input().split()))
b=[]
s=[0]*n
for i in range(n):
	b.append((a[i],i))
b.sort(reverse=True)
b.append((0,0))
MIN=10**9
for i in range(n):
	MIN=min(MIN,b[i][1])
	s[MIN]+=(i+1)*(b[i][0]-b[i+1][0])
for x in s:
	print(x)

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

# 実体Bと大きい順にループを回してindexを取得するためだけのC
B = [[a, i, 1] for i, a in enumerate(A)]
C = sorted(B, reverse=True)

# 自分より左側で最大となる値と位置
# 最大となる値が複数ある場合は最も左のものを採用
a_max, idx = 0, 0 # [value, idx]
left_max = [[0, 0] for i in range(N+1)] # [value, idx]
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: # indexだけ取得
  a, _, num = B[i] # 実体を取得、numは右側で同じ数になったとき、同じ山と見なして計算量削減
  if i == next_i:
    next_a, next_i = left_max[i] # 次の最大値であるnext_aになるまではこのiがsに追加される
    now_i = i
    ans[i] += (a - next_a) * num # 差分(a-next_a)をnum回分追加
    B[next_i][2] += num # 残った分はnext_iの石が消されるタイミングで消されるのでまとめる
  else:
    ans[now_i] += (a - next_a) * num
    B[next_i][2] += num

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

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")

def __starting_point():
    main()
__starting_point()

# 解説AC, add の部分を自分で作れなかった


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")


def __starting_point():
    main()

__starting_point()

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))
    return()
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)


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])

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]))


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:])))

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")


import typing
import sys
import math
import collections
import bisect
import itertools
import heapq
import decimal
import copy
import operator

# sys.setrecursionlimit(10000001)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

# buffer.readline()はこどふぉで死ぬ


def ni(): return int(sys.stdin.readline())
def ns(): return list(map(int, sys.stdin.readline().split()))
def na(): return list(map(int, sys.stdin.readline().split()))
def na1(): return list([int(x)-1 for x in sys.stdin.readline().split()])


# ===CODE===

def main():
    n = ni()
    ta = na()
    a = []
    for i, ai in enumerate(ta):
        a.append([ai, -i])
    a.sort(reverse=True)
    a.append([0, 0])
    cnt = [0 for _ in range(n)]

    idx = 0
    remain = a[0][0]
    minval = -a[0][1]
    while idx < n:
        while a[idx][0] == remain:
            idx += 1
        cnt[minval] += (remain-a[idx][0])*idx

        remain = a[idx][0]
        minval = min(minval, -a[idx][1])

    for c in cnt:
        print(c)


def __starting_point():
    main()

__starting_point()

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)

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])

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)

# coding: utf-8
# Your code here!
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]

#print(res)
while res:
    #print(num,cnt,idx)
    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")







'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
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))

#    print(d,cts)
    nms = sorted(list(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)
#        print(ans)

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

    for i in ans:
        print(i)



    return None

def __starting_point():
    main()

__starting_point()

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

from collections import defaultdict, deque
import math
import copy
from bisect import bisect_left, bisect_right
import heapq
import sys
# sys.setrecursionlimit(1000000)
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])
    # print(nums)
    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)

def __starting_point():
    main()


__starting_point()

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])

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')

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')


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))))


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)



"""

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

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

優先度付きキューで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)))

import copy

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

place_dict = {0:0}
num_list = []
ct_dict = {}
i = 1
for b in B:
  if b not in place_dict:
    place_dict[b] = i
    num_list.append(b)
    ct_dict[b] = 1
    i += 1
  else:
    ct_dict[b] += 1

tmp = 0
tasks = [(0,0)]
i = 0
for a in A:
  i += 1
  if tmp < a:
    tmp = a
    tasks.append((a,i))
    
#本処理
M = len(num_list)
#print(num_list)
ans = [0 for _ in range(N)]
j = M-1
ct_abv = 0
#print(ct_dict)
#print(tasks)
for i in range(len(tasks)-1,0,-1):
  tmp = 0
  nxt = tasks[i-1][0]
  while num_list[j] > nxt and j >= 0:
    ct_abv += ct_dict[num_list[j]]
    if j == 0:
      tmp += ct_abv * num_list[0]
    else:
      tmp += ct_abv * (num_list[j] - num_list[j-1])
    j -= 1
  ans[tasks[i][1]-1] = tmp
  #print(i,j,num_list[j],ct_abv)
  
print(*ans, sep = "\n")

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])
#Cumsum = [0]
#for i in D[::-1]:
#  Cumsum.append(i[0]+Cumsum[-1])
#Cumsum = Cumsum[::-1]
#print(Cumsum)
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]))



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]


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(list(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))))



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
#print(com, top_list, num_list)
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):
			#bisect.insort(com, a[i])
			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]])
	#print(total, (a[top_list[top + 1]] - a[top_list[top]])*stock,  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
	#print(com, top_list, num_list, stock)


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




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]))


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()

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')


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')


from collections import defaultdict

N = int(input())
*a, = list(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]))


N, = list(map(int, input().split()))
X = list(map(int, input().split()))
Y = []
for i in range(N):
    Y.append((X[i], -i))

sx = []
c = 0
d = dict()
for x in sorted(list(set(X))):
    sx.append(x)
    d[x] = c
    c += 1
sx.append(10**18)

count = [0]*(c+1)
for x in X:
    count[d[x]] += 1
for i in range(c-1, -1, -1):
    count[i] += count[i+1]

count2 = [0]*(c+1)
for i in range(c-1, -1, -1):
    count2[i] = count[i+1]*(sx[i+1]-sx[i])
for i in range(c-1, -1, -1):
    count2[i] += count2[i+1]



Y.sort()
R = []
while Y:
    y, j = Y.pop()
    if not R:
        R.append((y, -j))
    else:
#        print(y, j, R[-1])
        if y < R[-1][0] and -j < R[-1][1]:
            R.append((y, -j))



#print(count2)
#print(R)
RR = [0]*N
b = 0
bi = 0
for y, i in R[:]:
#    print(y, d[y], i, bi)
#    print(i, bi, count2[d[y]])

    RR[bi] = count2[d[y]]-b
    b = count2[d[y]]
    bi = i
RR[0] = sum(X)-sum(RR[1:])
for r in RR:
    print(r)


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)

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)

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()

#print(B)

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')

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)

#print(d, l)
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)

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)

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

def __starting_point():
    solve()
__starting_point()

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)

#if As = 1 2 1 3 2 4 2 5 8 1
#then sorted_iAs is:
#   i | 8 7 5 3 6 4 1 9 2 0
#   A | 8 5 4 3 2 2 2 1 1 1
#I'll look at:
#       x x x x     x     x
#where the next A decreases (or doesn't exist).

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')

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")


# coding: utf-8
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)  # 1-indexed
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:]))))


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 = list(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))))


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)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = [0]*n
    b = [v for v in a]
    b.append(0)
    b.sort()
    dic = {}
    cnt = []
    num = []
    for v in b:
        if v in dic:
            cnt[dic[v]] += 1
        else:
            p = len(cnt)
            cnt.append(1)
            dic[v] = p
            num.append(v)
    min_idx = [n]*len(cnt)
    for i, v in enumerate(a):
        if min_idx[dic[v]] > i:
            min_idx[dic[v]] = i
    for i in reversed(range(1, len(cnt))):
        dif = num[i] - num[i-1]
        ans[min_idx[i]] += dif * cnt[i]
        if min_idx[i-1] > min_idx[i]:
            min_idx[i-1] = min_idx[i]
        cnt[i-1] += cnt[i]
    for v in ans:
        print(v)

def __starting_point():
    main()
__starting_point()

import sys
input = sys.stdin.readline

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

B = [[A[i], i] for i in range(n)]
B.sort(key=lambda x:x[1])
B.sort(key=lambda x:x[0], reverse=True)
B.append([0, 0])

ANS = [0] * n
ind = n+1
m = 0
for i in range(n):
    if B[i][1] < ind:
        ind = B[i][1]
    m += 1
    ANS[ind] += m * (B[i][0]-B[i+1][0])

for i in ANS:
    print(i)

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)))


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()

#print(B)

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')

#1は一意
#2は小さい番号の石の数が大きくなるように、大きい番号の石を除きたい

#個数が同順のものを、番号小以外が個数が時点になるまで除いてから、番号少を除く
n = int(input())
a = list(map(int, input().split( )))

cnt = {}#keyは個数、要素は最小番号

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)
#print(mins)
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]
#ans[mins[-1][1]]=n*mins[-1][0]

for ai in ans:
    print(ai)
    





n = int(input())
a = list(map(int,input().split()))
l = [0]
ind = [-1]
for i in range(n):
    if a[i] > l[-1]:
        l.append(a[i])
        ind.append(i)
c1 = [0]*(len(l)+1)
c2 = [0]*(len(l)+1)
c1[0] = n
a.sort()
now = 0
for i in a:
    while now < len(l) and l[now] <= i:
        now += 1
    c1[now] -= 1
    c2[now-1] += i-l[now-1]
ans = [0]*n
for i in range(1,len(l)):
    c1[i] += c1[i-1]
    count = (l[i]-l[i-1])*c1[i]+c2[i-1]
    ans[ind[i]] = count

for i in ans:
    print(i)


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])

N = int(input())
A = list(map(int, input().split()))
d=dict()
for i, a in enumerate(A):
    j, cnt = d.get(a,(N,0))
    d[a] = min(i,j), cnt+1
P=[]
for k, v in d.items():
    P.append((k,v[0],v[1]))
P.sort(key=lambda x:x[0],reverse=True)
res=[0]*N
cnt=0
k=N-1
for i in range(len(P)-1):
    A0, i0, cnt0 = P[i]
    A1, i1, cnt1 = P[i+1]
    k = min(k,i0)
    cnt += cnt0
    res[k]+=(A0-A1)*cnt
A1, i1, cnt1 = P[-1]
res[min(i1,k)]+=A1*(cnt+cnt1)
print(*res,sep="\n")

# -*- coding: utf-8 -*-

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]
# ある値が最初に出現するindexを保持
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)
    # 今の値の先頭index
    mnidx = min(mnidx, D[a])
    ans[mnidx] += cnt
    # 今回の個数を次回以降用に追加
    prevcnt += C[a]
[print(a) for a in ans]


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')


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')

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)