Problem:


Score : 700 points

Problem Statement

Snuke loves constructing integer sequences.

There are N piles of stones, numbered 1 through N.
The pile numbered i consists of a_i stones.

Snuke will construct an integer sequence s of length Σa_i, as follows:

Among the piles with the largest number of stones remaining, let x be the index of the pile with the smallest index. Append x to the end of s.

Select a pile with one or more stones remaining, and remove a stone from that pile.

If there is a pile with one or more stones remaining, go back to step 1. Otherwise, terminate the process.

We are interested in the lexicographically smallest sequence that can be constructed. For each of the integers 1,2,3,...,N, how many times does it occur in the lexicographically smallest sequence?

Constraints

1 ≤ N ≤ 10^{5}

1 ≤ a_i ≤ 10^{9}

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{N}

Output

Print N lines. The i-th line should contain the number of the occurrences of the integer i in the lexicographically smallest sequence that can be constructed.

Sample Input 1

2
1 2

Sample Output 1

2
1

The lexicographically smallest sequence is constructed as follows:

Since the pile with the largest number of stones remaining is pile 2, append 2 to the end of s. Then, remove a stone from pile 2.

Since the piles with the largest number of stones remaining are pile 1 and 2, append 1 to the end of s (we take the smallest index). Then, remove a stone from pile 2.

Since the pile with the largest number of stones remaining is pile 1, append 1 to the end of s. Then, remove a stone from pile 1.

The resulting sequence is (2,1,1). In this sequence, 1 occurs twice, and 2 occurs once.

Sample Input 2

10
1 2 1 3 2 4 2 5 8 1

Sample Output 2

10
7
0
4
0
3
0
2
3
0



Sample input:
2
1 2


Sample output:
2
1

Submission status: Wrong Answer

Solution code:
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], x[0]))
b.append((0, 0))
ans = [0]*(n+2)
c = b[0][0]
for i in range(n):
    if b[i][1] == b[i+1][1]:
        continue
    ans[c] += (i+1)*(b[i][1]-b[i+1][1])
    c = b[i+1][0]
for i in range(1, n+1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
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], x[0]))
ans = [0]*(n+1)
c = b[0][0]
for i in range(n-1):
    if b[i][1] == b[i+1][1]:
        continue
    ans[c] += (i+1)*(b[i][1]-b[i+1][1])
    c = b[i+1][0]
ans[1] += sum(a) - sum(ans)
for i in range(1, n+1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
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], x[0]))
ans = [0]*(n+1)
c = b[0][0]
for i in range(n-1):
    if b[i][1] == b[i+1][1]:
        continue
    ans[c] = (i+1)*(b[i][1]-b[i+1][1])
    c = b[i+1][0]
ans[1] = n
for i in range(1, n+1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
A = [0] + LI()

B = list(set(A))
B.sort(reverse=True)
d = {}
for b in B:
    d[b] = []
for i in range(N+1):
    d[A[i]].append(i)

ANS = [0]*(N+1)
max_A = B[0]
max_index = d[B[0]][0]
r = len(d[B[0]])
for i in range(1,len(B)):
    if d[B[i]][0] < max_index:
        ANS[max_index] = (max_A-B[i])*r
        max_A = B[i]
        max_index = d[B[i]][0]
    r += len(d[B[i]])

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

Submission status: Wrong Answer

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

L = list(range(N))

ZIP = zip(A, L)

ZIP = sorted(ZIP, reverse = True)

A, L = zip(*ZIP)

ans = []

for i in range(N-1):
    ans.append((A[i] - A[i+1]) * (i + 1))
ans.append(sum(A) - sum(ans))

ZIP = zip(L, ans)

ZIP = sorted(ZIP)

L, ans = zip(*ZIP)

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
'''
自宅用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(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]
        ans[ps] += d[i]*(i-na)
        if i == na:
            lc -= 1
            na = cts[lc][0]
            ans[ps] += sm*(i-na)
            ps = cts[lc][1]
            if lc == 0:
                break

    ans[0] = tot-sum(ans[1::])
    for i in ans:
        print(i)



    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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
for index, (original_index, A) in enumerate(sorted_iAs):
    if index == N - 1:
        ans[original_index] += A * (index + 1)
    elif sorted_iAs[index + 1][1] < A:
        next_A = sorted_iAs[index + 1][1]
        ans[original_index] += (A - next_A) * (index + 1)

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=sorted([(i,a) for i,a in enumerate(A)],key=lambda x:x[1])
class SegTreeMax:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[-self.INF]*(2*self.N0)
    def update(self,i,x):
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=max(self.data[i*2+1],self.data[i*2+2])
    def max(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
class BIT:
    def __init__(self,N):
        self.N=N
        self.data=[0]*(N+1)
    def add(self,i,x):
        i+=1
        while i<=self.N:
            self.data[i]+=x
            i+=i&-i
    def sum(self,a,b):
        if a>0:
            r=self.sum(0,b)-self.sum(0,a)
        else:
            r=0
            i=b
            while i>0:
                r+=self.data[i]
                i-=i&-i
        return r
d,d2=[0]*N,[0]*N
s=SegTreeMax(N+1)
s.update(0,0)
for i,a in B:
    m=s.max(0,i+1)
    d[i]=A[i] if i>0 and m==0 else m
    s.update(i+1,a)
b=BIT(N)
for i,a in B[::-1]:
    b.add(i,1)
    d2[i]=b.sum(i,N)
r=[(A[i]-d[i])*d2[i] for i in range(N)]
print(*[r[i] if i>0 else sum(A)-sum(r[1:]) for i in range(N)],sep='\n')

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=sorted([(i,a) for i,a in enumerate(A)],key=lambda x:x[1])
class SegTreeMax:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[-self.INF]*(2*self.N0)
    def update(self,i,x):
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=max(self.data[i*2+1],self.data[i*2+2])
    def max(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
class BIT:
    def __init__(self,N):
        self.N=N
        self.data=[0]*(N+1)
    def add(self,i,x):
        i+=1
        while i<=self.N:
            self.data[i]+=x
            i+=i&-i
    def sum(self,a,b):
        if a>0:
            r=self.sum(0,b)-self.sum(0,a)
        else:
            r=0
            i=b
            while i>0:
                r+=self.data[i]
                i-=i&-i
        return r
d,d2=[0]*N,[0]*N
s=SegTreeMax(N+1)
s.update(0,0)
for i,a in B:
    d[i]=s.max(0,i+1)
    s.update(i+1,a)
b=BIT(N)
for i,a in B[::-1]:
    b.add(i,1)
    d2[i]=b.sum(i,N)
print(*[(A[i]-d[i])*d2[i] for i in range(N)],sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))

inf = 10**10
S = sorted(list(set(A)))
dic = {s:inf for s in S}
cnt = {s:0 for s in S}
for i, a in enumerate(A):
    dic[a] = min(i,dic[a])
    cnt[a] += 1

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

ans = [0]*N
S = [0] + S
for ps, s in zip(S[:-1][::-1],S[::-1]):
    ans[dic[s]] = (s-ps) * cnt[s]

[print(a) for a in ans]

Submission status: Wrong Answer

Solution code:
# 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
idx = n-1
v = res[-1][0]

#print(res)
while res:
    #print(num,cnt,idx)
    ans[idx] = (v-res[-1][0])*cnt
    v = res[-1][0]

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


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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
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]
    target[i+1][1] = min(target[i+1][1], b)

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

Submission status: Wrong Answer

Solution code:
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 = 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]

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

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
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 = 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]

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

Submission status: Wrong Answer

Solution code:
# 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[-1])
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])

Submission status: Wrong Answer

Solution code:
# 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()
left = [0] * N
right = [0] * N
X = 0
for i, a in enumerate(A):
    if a > X:
        left[i] = a - X
        X = a

target = []
for i, a in enumerate(A[::-1]):
    index = bisect_left(target, a)
    insort(target, a)
    right[N-1-i] = i + 1 - index
    
answer = [l * r for l, r in zip(left, right)]
print('\n'.join(map(str, answer)))
# 22

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
from itertools import accumulate

n, *A = map(int, read().split())
S = sorted(set(A))
l = len(S)
C = [0]*l
D = {e:i for i, e in enumerate(S)}
K = [-1]*l
for i, a in enumerate(A):
  idx = D[a]
  if K[idx] == -1:
    K[idx] = i
  C[idx] += 1
S = [0] + S
C = list(accumulate(C[::-1]))[::-1]
L = [0]*n
for i, k in enumerate(K):
  L[k] = (S[i+1]-S[i]) * C[i]
print(*L, sep="\n")

Submission status: Wrong Answer

Solution code:
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
# 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, 0))
    nums.sort(key=lambda x: -x[0] * INF + x[1])
    # print(nums)
    mx = INF
    ans = [0 for i in range(n+1)]
    tmp_tgt = 0
    through = 0
    for a,b in nums:
        if a != mx:
            diff = mx - a



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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

from collections import defaultdict
d = defaultdict(lambda: [])
for i,a in enumerate(A):
    d[a].append(i)

sd = sorted(d.items(), reverse=True)
ans = [0] * N
s = 0
for (v1,a1),(v2,a2) in zip(sd, sd[1:]):
    v = v1-v2
    s += len(a1)
    ans[a1[0]] = v*s
ans[0] = sd[-1][0] * N

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

Submission status: Wrong Answer

Solution code:
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]]
for r in res[1: ]: print(r)

Submission status: Wrong Answer

Solution code:
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[1]
for r in res[1: ]: print(r)

Submission status: Wrong Answer

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

while i < n:
    while aa[i][1] >= i_prev:
        i += 1

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

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

Submission status: Wrong Answer

Solution code:
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, n]]
v_prev, i_prev = aa[0]
i = 0
ans = [0] * n
while i < n:
    while aa[i][0] == v_prev:
        i += 1

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

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

Submission status: Wrong Answer

Solution code:
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, n]]
v_prev, i_prev = aa[0]
i = 0
sm = 0
cnt = 0
ans = [0] * n
while i < n:
    while aa[i][0] == v_prev:
        sm += aa[i][0]
        cnt += 1
        i += 1

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

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

Submission status: Wrong Answer

Solution code:
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
for x, y in zip(value[:-1], value[1:]):
    i = a_to_i[x]
    cnt += C[x]
    ans[i] += (x - y) * cnt

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

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = [0]*N
    lis = [0]*N
    for i,a in enumerate(A):
        lis[i] = [a,i]
    lis.sort(key=lambda x: (-x[0],-x[1]))
    lis.append([0,0])
    for i in range(N):
        if lis[i][0]==lis[i+1][0]:
            continue
        else:
            ans[lis[i][1]] = i+lis[i][0]-lis[i+1][0] 
    return ans
print(*solve(),sep='\n')

Submission status: Wrong Answer

Solution code:
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)
    print(ans)
ans[0] += N * aa[0]
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
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]:
    c = compress[a[i]]
    cnt[c] += 1
    idx[c] = 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')

Submission status: Wrong Answer

Solution code:
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]:
    c = compress[a[i]]
    cnt[c] += 1
    idx[c] = 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
print(*ans, sep='\n')

Submission status: Wrong Answer

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

print(left_max)
ans = [0] * (N+1)
next_i = C[0][1]
print(B)
print(C)
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')

Submission status: Wrong Answer

Solution code:
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
  elif i > now_i:
    ans[now_i] += (a - next_a) * num
    B[next_i][2] += num

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

Submission status: Wrong Answer

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

ans = [0]*N
max_ = 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
        max_ = a[i]

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

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

Submission status: Wrong Answer

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

ans = [0]*N
max_ = 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
        max_ = a[i]

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

Submission status: Wrong Answer

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

B = []
for i, a in enumerate(A):
    B.append((a, i+1))

d = {}
for x, y in B:
    if x in d:
        d[x] = min(d[x], y)
    else:
        d[x] = y

C = []
for x, y in B:
    C.append((x, y, d[x]))
C.sort(key=lambda x: (-x[0], -x[1]))
C.append((0, 0, 0))
#print(C)


ans = [0]*n
for i in range(len(C)-1):
    ans[C[i][2]-1] = (i+1)*(C[i][0]-C[i+1][0])

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[[a[i],i] for i in range(n)]
b.sort(key=lambda x:(x[0],x[1]),reverse=1)
c=[0]
for i in a:c.append(max(c[-1],i))
ans=[0]*n
for i in range(n):
  j=b[i][1]
  if c[j]<c[j+1]:
    ans[j]=(i+1)*(c[j+1]-c[j])
print(*ans)

Submission status: Wrong Answer

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

cnt = {'0' : 0}
idx = {'0' : None}
for i, ai in enumerate(a):
    key = str(ai)
    cnt.setdefault(key, 0)
    idx.setdefault(key, i + 1)
    cnt[key] += 1
    idx[key] = min(idx[key], i + 1)

ans = [0] * (N + 1)
cnt_tmp = 0
idx_tmp = N
q = sorted(cnt.keys())[::-1]
for i in range(len(q) - 1):
    src = q[i]
    dst = q[i + 1]
    # print("#", src, dst)
    cnt_tmp += cnt[src]
    idx_tmp = min(idx_tmp, idx[src])
    #
    ans[idx_tmp] += (int(src) - int(dst)) * cnt_tmp

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#座標圧縮
#a=list
#flag=0...座圧済みa flag=1...座圧指標dict
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]

#-----BinaryIndexedTree-----(0-indexed)
#O(logN)で累積和取得と値の更新
#add(i,x)...i番目にxを加算
#sum(i,j)...[i,j]の累積和を取得
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j)
    if i!=0:a-=self.sum_sub(i-1)
    return a

n=int(input())
a=list(map(int,input().split()))
d=position_zip(a,1)
b=[a[0]]
for i in a[1:]:b.append(max(b[-1],i))
ans=[0]*n
bit=BinaryIndexedTree(n)
for i in range(n-1,0,-1):
  bit.add(d[a[i]],1)
  if b[i-1]<b[i]:ans[i]=(b[i]-b[i-1])*bit.sum(d[b[i]],n-1)
ans[0]=sum(a)-sum(ans)
print(*ans)

Submission status: Wrong Answer

Solution code:
#座標圧縮
#a=list
#flag=0...座圧済みa flag=1...座圧指標dict
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]

#-----BinaryIndexedTree-----(0-indexed)
#O(logN)で累積和取得と値の更新
#add(i,x)...i番目にxを加算
#sum(i,j)...[i,j]の累積和を取得
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j)
    if i!=0:a-=self.sum_sub(i-1)
    return a

n=int(input())
a=list(map(int,input().split()))
d=position_zip(a,1)
b=[a[0]]
for i in a[1:]:b.append(max(b[-1],i))
ans=[0]*n
bit=BinaryIndexedTree(n)
for i in range(n-1,0,-1):
  if b[i-1]<b[i]:
    ans[i]=(b[i]-b[i-1])+(b[i]-b[i-1])*bit.sum(d[b[i]],n-1)
  bit.add(d[a[i]],1)
ans[0]=sum(a)-sum(ans)
print(*ans)

Submission status: Wrong Answer

Solution code:
#座標圧縮
#a=list
#flag=0...座圧済みa flag=1...座圧指標dict
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]

#-----BinaryIndexedTree-----(0-indexed)
#O(logN)で累積和取得と値の更新
#add(i,x)...i番目にxを加算
#sum(i,j)...[i,j]の累積和を取得
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j)
    if i!=0:a-=self.sum_sub(i-1)
    return a

n=int(input())
a=list(map(int,input().split()))
d=position_zip(a,1)
b=[a[0]]
for i in a[1:]:b.append(max(b[-1],i))
ans=[0]*n
bit=BinaryIndexedTree(n)
for i in range(n-1,0,-1):
  if b[i-1]<b[i]:
    ans[i]=(b[i]-b[i-1])+bit.sum(d[a[i]],n-1)
  bit.add(d[a[i]],1)
ans[0]=sum(a)-sum(ans)
print(*ans)

Submission status: Wrong Answer

Solution code:
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()
r = n - 1
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)