AtCoder Regular Contest 069 - Frequency

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

Starter code:

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


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


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


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


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


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


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)


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


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


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


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


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)


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


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


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

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


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)


from collections import defaultdict, Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
values = reversed(sorted(set(a)))
s = 0
m = 0
above = dict()
n_above = dict()
for v in values:
	above[v] = s
	n_above[v] = m
	s += c[v] * v
	m += c[v]
above[0] = s
n_above[0] = m
m = 0
u = [0]
for v in a:
	if v > m:
		u.append(v)
		m = v
r = defaultdict(int)
last = 0
for (j, v) in enumerate(u):
	r[v] = last - (above[v] - n_above[v] * v)
	last = above[v] - n_above[v] * v
m = 0
for v in a:
	if v > m:
		print(r[v])
		m = v
	else:
		print(0)


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


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


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


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


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


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


import typing
import sys
import math
import collections
import bisect
import itertools
import heapq
import decimal
import copy
import operator
INF = 10 ** 20
MOD = 10 ** 9 + 7

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

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)


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)


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


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


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)


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


N = int(input())
A = list(map(int, input().split()))
t = A[0]
indices = [0]
seq = [t]
for i in range(1, N):
	if A[i] > t:
		t = A[i]
		indices.append(i)
		seq.append(t)
M = len(seq)
delta = [seq[0]] + [seq[i + 1] - seq[i] for i in range(M - 1)]
temp = [0] * M
count = [0] * M
from bisect import bisect_left
for a in A:
	p = bisect_left(seq, a)
	count[p] += a - seq[p]
	temp[p] += 1
t = 0
for i in reversed(range(M)):
	t += temp[i]
	temp[i] = t
for i in range(M):
	count[i] += temp[i] * delta[i]
result = [0] * N
for (i, c) in zip(indices, count):
	result[i] = c
for r in result:
	print(r)


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


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


n_mou = int(input())
l_mou = list(map(int, input().split()))
l_mou_ind = [[l_mou[i], i] for i in range(n_mou)]
l_mou_ind.sort()
l_ans = [0 for i in range(n_mou)]
l_ans[0] = l_mou_ind[0][0] * n_mou
min_index = l_mou_ind[-1][1]
for i in range(n_mou - 1, 0, -1):
	min_index = min(min_index, l_mou_ind[i][1])
	if l_mou_ind[i - 1][0] != l_mou_ind[i][0]:
		l_ans[min_index] += (l_mou_ind[i][0] - l_mou_ind[i - 1][0]) * (n_mou - i)
for i in range(n_mou):
	print(l_ans[i])


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)


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)


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


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)


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


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


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)

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)


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


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


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


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)


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


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7

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

def II():
	return int(input())

def LS():
	return input().split()

def S():
	return input()

def main():
	n = II()
	a = LI()
	b = [(a[i], i) for i in range(n)]
	b.sort()
	b.reverse()
	r = [0] * n
	s = sum(a)
	t = inf
	for i in range(n):
		(ai, bi) = (b[i][0], b[i][1])
		if bi == 0:
			r[0] += s
			break
		ti = (ai - b[i + 1][0]) * (i + 1)
		if t > bi:
			t = bi
		r[t] += ti
		s -= ti
	return '\n'.join(map(str, r))
print(main())


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)


from collections import Counter
N = int(input())
S = list(map(int, input().split()))
T = []
for i in range(N):
	T.append((i, S[i]))
U = sorted(T, key=lambda x: x[1], reverse=True)
Ans = [0] * N
(c, v) = (0, 10 ** 10)
for i in range(N - 1):
	c += 1
	v = min(v, U[i][0])
	if U[i][1] == U[i + 1][1]:
		continue
	else:
		Ans[v] += (U[i][1] - U[i + 1][1]) * c
else:
	Ans[0] = 0
	Ans[0] = sum(S) - sum(Ans)
for i in range(N):
	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')


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)


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


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)


n = int(input())
an = list(map(int, input().split()))
sa = sorted(((a, i) for (i, a) in enumerate(an)), reverse=True)
sa.append((0, 0))
result = [0] * n
(prev_a, min_i) = sa[0]
for (j, (a, i)) in enumerate(sa[1:]):
	result[min_i] += (j + 1) * (prev_a - a)
	min_i = min(min_i, i)
	prev_a = a
for cnt in result:
	print(cnt)


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


def BS(th, a):
	top = len(th)
	btm = 0
	while top > btm:
		mid = (top + btm) // 2
		if th[mid] < a <= th[mid + 1]:
			return mid
		elif a <= th[mid]:
			top = mid
		else:
			btm = mid
N = int(input())
A = [int(i) for i in input().split()]
th = [0]
num_th = []
rem = []
max_i = 0
nonzeros = dict()
for (i, a) in enumerate(A):
	if a > th[-1]:
		th.append(a)
		num_th.append(1)
		rem.append(0)
		nonzeros[i] = max_i
		max_i += 1
	else:
		j = BS(th, a)
		if j - 1 >= 0:
			num_th[j - 1] += 1
		rem[j] += a - th[j]
for i in range(len(num_th) - 1, 0, -1):
	num_th[i - 1] += num_th[i]
for i in range(N):
	if i in nonzeros:
		ans = (th[nonzeros[i] + 1] - th[nonzeros[i]]) * num_th[nonzeros[i]] + rem[nonzeros[i]]
		print(ans)
	else:
		print(0)


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


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


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


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


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]


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


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)


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


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


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)


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


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)


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


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


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)


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


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)


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


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


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


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


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


def readln():
	_res = list(map(int, str(input()).split(' ')))
	return _res
n = int(input())
a = readln()
c = sorted([[-a[i], i] for i in range(0, n)])
ans = [0 for i in range(0, n)]
front = c[0][1]
for i in range(1, n):
	ans[front] = ans[front] + i * (c[i][0] - c[i - 1][0])
	if front > c[i][1]:
		front = c[i][1]
ans[front] = ans[front] + n * -c[n - 1][0]
for a in ans:
	print(a)


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


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)


N = int(input())
A = map(int, input().split())
S = sorted([[a, i] for (i, a) in enumerate(A)], key=lambda x: x[0], reverse=True)
S.append([0, N])
B = [0 for i in range(N)]
num = S[0][1]
for i in range(1, N + 1):
	if S[i - 1][0] > S[i][0]:
		B[num] += (S[i - 1][0] - S[i][0]) * i
	num = min(num, S[i][1])
for b in B:
	print(b)


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)


N = int(input())
a = list(map(int, input().split()))
b = [(a[i], i, 0) for i in range(N)]
b.sort(key=lambda x: (-x[0], x[1]))
mini = 0
for i in range(N - 1):
	if b[i][1] < b[mini][1]:
		mini = i
	b[mini] = (b[mini][0], b[mini][1], b[mini][2] + (b[i][0] - b[i + 1][0]) * (i + 1))
if b[N - 1][1] < b[mini][1]:
	mini = N - 1
b[mini] = (b[mini][0], b[mini][1], b[mini][2] + b[N - 1][0] * N)
b.sort(key=lambda x: x[1])
for x in b:
	print(x[2])


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


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


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


def solve():
	n = int(input())
	work_array = [[a, b] for (a, b) in zip([int(i) for i in input().split()], [j for j in range(0, n)])]
	ans_list = [0] * n
	work_array.sort(reverse=True)
	last_num = work_array[0][0]
	min_index = work_array[0][1]
	for counter in range(n):
		current_num = work_array[counter][0]
		if last_num != current_num:
			ans_list[min_index] += counter * (last_num - current_num)
			last_num = current_num
		min_index = min(min_index, work_array[counter][1])
	ans_list[min_index] += (counter + 1) * last_num
	print('\n'.join([str(c) for c in ans_list]))
solve()


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(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)
	ans[0] = tot - sum(ans[1:])
	for i in ans:
		print(i)
	return None

def __starting_point():
	main()
__starting_point()


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]


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


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


from functools import cmp_to_key
n = int(input())
a = list(map(int, input().split()))

def group(a):
	d = {}
	for (i, x) in enumerate(a):
		d.setdefault(x, []).append(i)
	return list(map(lambda x: [x[0], x[1][0], len(x[1])], sorted(d.items(), key=cmp_to_key(lambda x, y: x[0] - y[0]), reverse=True)))
ans = [0] * n
g = group(a)
g.append([0, 0, 0])
for (c, n) in zip(g[:-1], g[1:]):
	ans[c[1]] += (c[0] - n[0]) * c[2]
	n[1] = min(c[1], n[1])
	n[2] += c[2]
[print(a) for a in ans]


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


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


n = int(input())
lis = list(map(int, input().split()))
key = lis[0]
num = [0]
li = [key]
for i in range(1, n):
	if lis[i] > key:
		key = lis[i]
		num.append(i)
		li.append(key)
m = len(li)
nu = [li[0]] + [li[i + 1] - li[i] for i in range(m - 1)]
he = [0] * m
cou = [0] * m
from bisect import bisect_left
for k in lis:
	sen = bisect_left(li, k)
	cou[sen] += k - li[sen]
	he[sen] += 1
key = 0
for i in reversed(range(m)):
	key += he[i]
	he[i] = key
for i in range(m):
	cou[i] += he[i] * nu[i]
ans = [0] * n
for (i, c) in zip(num, cou):
	ans[i] = c
for r in ans:
	print(r)


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


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


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


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)


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)


from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
setrecursionlimit(1000000)
N = read()
a = reads()
b = [(-a[i], i) for i in range(N)]
b.sort()
b.append((0, -1))
result = [0] * N
m = b[0][1]
j = 0
for i in range(1, N + 1):
	if b[j][0] != b[i][0]:
		result[m] += (b[i][0] - b[j][0]) * i
		j = i
	m = min(m, b[i][1])
for i in range(N):
	print(result[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()
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')


from collections import defaultdict
N = int(input())
src = list(map(int, input().split()))
dic = defaultdict(lambda : (N, 0))
for (i, a) in enumerate(src):
	(m, n) = dic[a]
	dic[a] = (min(m, i), n + 1)
order = sorted(list(dic.items()))
hist = [0] * N
while True:
	(a1, (m1, n1)) = order.pop()
	if not order:
		hist[m1] += n1 * a1
		break
	(a2, (m2, n2)) = order[-1]
	hist[m1] += n1 * (a1 - a2)
	order[-1] = (a2, (min(m1, m2), n1 + n2))
print(*hist, sep='\n')


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)
ans = [0 for _ in range(N)]
j = M - 1
ct_abv = 0
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(*ans, sep='\n')


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)


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


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