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:
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 = n
for i in range(n - 1, -1, -1):
    if A[i - 1][0] < A[i][0]:
        ans[A[i][1]] = (A[i][0] - A[i - 1][0]) * (n - i)
    min_ind = min(min_ind, A[i][1])

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

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
while True:
    l = bisect_left(A, (A[r][0], -INF))
    idx = A[l][1]
    if l:
        ans[idx] = (A[l][0] - A[l - 1][0]) * (n - l)
    else:
        ans[idx] = (A[l][0] - 0) * (n - l)
        break
    r = l - 1

for j in ans:
    print(j)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

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

for i in range(N):
    idx[a[i]].append(i)

acc = [a[0]]

for i in range(1, N):
    acc.append(max(acc[-1], a[i]))

ans = [0]*N
now = max(a)

while True:
    i = idx[now][0]
    
    if i==0:
        ans[0] = sum(a)-sum(ans)
        break
    
    ans[i] += (now-acc[i-1])*len(idx[now])
    
    for j in idx[now]:
        idx[acc[i-1]].append(j)
        
    now = acc[i-1]

for ans_i in ans:
    print(ans_i)

Submission status: Wrong Answer

Solution code:
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)
inf.sort(reverse=True)
cnt = [0]*N
for a,i in inf:
  B.bit_add(i,1)
  cnt[i] = B.bit_sum(N-1)-B.bit_sum(i-1)

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=sorted([[a[i],i]for i in range(n)],key=lambda x:(-x[0],x[1]))
if n==1:
    print(a[0])
else:
    c=1
    t=[0]*n
    while 1:
        if len(s)==1:
            t[s[0][1]]=c*(s[0][0])
            break
        elif s[0][1]>s[1][1] and s[0][0]!=s[1][0]:
            t[s[0][1]]=c*(s[0][0]-s[1][0])
            c+=1
            s.pop(0)
        elif s[0][0]==s[1][0]:
            p=s[0][1]
            while len(s)!=1:
                if s[0][0]==s[1][0]:
                    c+=1
                    s.pop(0)
                else:
                    t[p]=c*(s[0][0]-s[1][0])
                    c+=1
                    s.pop(0)
                    break
            else:
                t[p]+=sum(a)-sum(t)
                break
        else:
            t[s[0][1]]+=sum(a)-sum(t)
            break
    for i in t:
        print(i)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

    for r in ans[1:]:
        print(r)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

    r = INF
    same = 0
    q = []
    for i in range(len(ai)-1):
        if r > ai[i][1]:
            d = ai[i][0] - ai[i+1][0]
            ans[ai[i][1]] = d * (same + 1)
            r = ai[i][1]
            same += 1
            while q and q[0] > ai[i+1][0]:
                b = heapq.heappop(q)
                ans[ai[i][1]] += b - ai[i+1][0]
                same += 1
        else:
            heapq.heappush(q, ai[i][0])

    for r in ans:
        print(r)
    # return ans


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = Counter(A)
# 重複削除して降順、この順に処理していく
unique = sorted(set(A), reverse=1) + [0]
# ある値が最初に出現するindexを保持
D = {}
for i in range(N-1, -1, -1):
    D[A[i]] = i

ans = [0] * N
prevcnt = 0
mnidx = INF
for i, a in enumerate(unique[:-1]):
    nxta = unique[i+1]
    # 今回の位置が選ばれる回数 = 次の値との差分 * 今の値の個数
    cnt = (a - nxta) * (C[a] + prevcnt)
    # 今の値の先頭index
    mnidx = min(mnidx, D[a])
    ans[mnidx] = cnt
    # 今回の個数を次回以降用に追加
    prevcnt += C[a]
[print(a) for a in ans]

Submission status: Wrong Answer

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

ans=[0]*N

kkk=0
for i in range(len(data)-1,0,-1):
    
    zzz=data[i][0]
    while kkk<N and B[kkk]>=zzz:
        kkk+=1
        
    ans[data[i][1]]=(zzz-data[i-1][0])*kkk
ans[0]=sum(A)-sum(ans)

for u in ans:
    print(u)

Submission status: Wrong Answer

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

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

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

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

#個数、最小番号、番号の数    
mins = [[k,cnt[k][0],cnt[k][1]] for k in cnt]
mins.append([0,0,0])
mins.sort(reverse = True)

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)

Submission status: Wrong Answer

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

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

cnt = {}

for i in range(n):
    if a[i] in cnt:
        cnt[a[i]].append(i)
    else:
        cnt[a[i]] = [i]
for k in cnt:
    cnt[k].sort()
mins = [[k,cnt[k][0],len(cnt[k])] 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)

Submission status: Wrong Answer

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

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

cnt = {}

for i in range(n):
    if a[i] in cnt:
        cnt[a[i]].append(i)
    else:
        cnt[a[i]] = [i]
for k in cnt:
    cnt[k].sort()
mins = [[k,cnt[k][0],len(cnt[k])] 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
    try:
        mins[i+1][2]+=l
    except:
        print(mins,i)
for a in ans:
    print(a)

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

Submission status: Wrong Answer

Solution code:
import collections
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)
for i in range(n):
  j=n-1-i
  if A[j]<=M[j]:
    D[A[j]]+=1
  else:
    Ans[j]=(A[j]-M[j])*(D[A[j]]+1)
    D[M[j]]+=D[A[j]]+1
for a in Ans:
  print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(range(n))
s = 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)
print(*ans,sep="\n")

Submission status: Wrong Answer

Solution code:
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
while i < N-1:
    num = A[i][1]
    while i < N-1 and A[i][0] == A[i+1][0]:
        if num > A[i+1][1]:
            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])

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())

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


ans = [0] * N

q = []

for i in range(N):
    heapq.heappush(q,[a[i],i])

last = 0

while len(q) > 0:

    while len(q) > 0 and q[0][0] <= last:
        heapq.heappop(q)
    if len(q) == 0:
        break

    now = heapq.heappop(q)
    num = now[1]

    ans[num] = ( now[0] - last ) * (len(q)+1)
    last = now[0]

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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
    for k in range(len(d)-1):
        x,y,z=d[k]
        l+=z
        ans[y]=(x-d[k+1][0])*l
    for i in ans:
        print(i)
main()

Submission status: Wrong Answer

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()

class BinaryIndexedTree():
    def __init__(self,N):
        self.N = N
        self.bit = [0]*(self.N+1)

    def add(self,a,w):
        a += 1
        x = a
        while x <= self.N:
            self.bit[x] += w
            x += x & -x

    def sum(self,a):
        a += 1
        tmp = 0
        x = a
        while x > 0:
            tmp += self.bit[x]
            x -= x & -x
        return tmp


BIT = BinaryIndexedTree(N)
aa = inpl()

i2a = sorted(list(set(aa)))
a2i = defaultdict(int)
for i,a in enumerate(i2a):
    a2i[a] = i


koho = [0]*N
ba = 0
for i,a in enumerate(aa):
    if ba < a:
        koho[i] = a- ba
        ba = a


ans = [0]*N
for ri,a in enumerate(reversed(aa)):
    i = N-1-ri
    BIT.add(a2i[a], 1)

    if koho[i]:
        ans[i] =  (BIT.sum(N-1) - BIT.sum(a2i[a]-1)) * koho[i]

ans[0] += sum(aa) - sum(ans)

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

Submission status: Wrong Answer

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()

class BinaryIndexedTree():
    def __init__(self,N):
        self.N = N
        self.bit = [0]*(self.N+1)

    def add(self,a,w):
        a += 1
        x = a
        while x <= self.N:
            self.bit[x] += w
            x += x & -x

    def sum(self,a):
        a += 1
        tmp = 0
        x = a
        while x > 0:
            tmp += self.bit[x]
            x -= x & -x
        return tmp


BIT = BinaryIndexedTree(N)
aa = inpl()

i2a = sorted(list(set(aa)))
a2i = defaultdict(int)
for i,a in enumerate(i2a):
    a2i[a] = i


koho = [0]*N
ba = 0
for i,a in enumerate(aa):
    if ba < a:
        koho[i] = a- ba
        ba = a


ans = [0]*N
for ri,a in enumerate(reversed(aa)):
    i = N-1-ri
    BIT.add(a2i[a], 1)

    if koho[i]:
        ans[i] =  (BIT.sum(N-1) - BIT.sum(a2i[a]-1)) * koho[i]

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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

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

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

Submission status: Wrong Answer

Solution code:
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-1
            mini = min(mini, a[j][0])
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,a=open(0)
c,d={},{}
for j,i in enumerate(map(int,('0 '+a).split())):
  if not i in d:d[i]=j
  c[i]=c.get(i,0)+1
i=sorted(d)[::-1]
a=[0]*int(n)
for i,j in zip(i,i[1:]):
  a[d[i]-1]=(i-j)*c[i]
  c[j]+=c[i]
print(*a)

Submission status: Wrong Answer

Solution code:
n,a=open(0)
c,d={},{}
for j,i in enumerate(map(int,('0 '+a).split())):
  if not i in d:d[i]=j
  c[i]=c.get(i,0)+1
i=sorted(c)[::-1]
a=[0]*int(n)
for i,j in zip(i,i[1:]):
  a[d[i]-1]=(i-j)*c[i]
  c[j]+=c[i]
print(*a)

Submission status: Wrong Answer

Solution code:
n,a=open(0)
c,d={},{}
for j,i in enumerate(map(int,('0 '+a).split())):
  if not i in d:d[i],m=j,i
  c[i]=c.get(i,0)+1
i=sorted(d)[::-1]
a=[0]*int(n)
for i,j in zip(i,i[1:]):
  a[d[i]-1]=(i-j)*c[i]
  c[j]+=c[i]
print(*a)

Submission status: Wrong Answer

Solution code:
n,a=open(0)
*a,=map(int,('0 '+a).split())
c,d={},{}
m=-1
for j,i in enumerate(a):
  if i>m:d[i],m=j,i
  c[i]=c.get(i,0)+1
i=sorted(d)[::-1]
a=[0]*int(n)
for i,j in zip(i,i[1:]):
  a[d[i]-1]=(i-j)*c[i]
  c[j]+=c[i]
print(*a)

Submission status: Wrong Answer

Solution code:
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 * (now - A[j][0])

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [(0, 0)] + [(a, i) for i, a in enumerate(A)]

A.sort()
ans = [0] * N

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3.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) 
# Add w to ax 
def bit_add(x, w):
    while x <= n:
        bit[x] += w
        x += x & -x

# Sum a1 to ax 
def bit_sum(x):
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= x & -x
    return ret

big_rgt = [0] * n
for _, index in awid:
    bit_add(index+1, 1)
    big_rgt[index] = bit_sum(n) - bit_sum(index)

min_a = 0
for i, item in enumerate(a):
    if item > min_a:
        ans = (item - min_a) * big_rgt[i]
        print(ans)
        min_a = item
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
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])
#[::-1]
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,m
ans[0]+=sum(a)-sum(ans)
#print(n,a)
#print(*ans)
for i in ans:print(i)

Submission status: Wrong Answer

Solution code:
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])
#[::-1]
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,m
ans[0]+=a[0]*n
for i in ans:print(i)

Submission status: Wrong Answer

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

tmp = []
ans = []
m = 0

for i in range(n):
    if m < a[i]:
        tmp.append([i,a[i]])
        ans.append([i,0])
        m = a[i]
    else:
        j = 0
        k = a[i]
        l = 0
        while k > 0:
            ans[j][1] += min(k,tmp[j][1]-l)
            k -= tmp[j][1]
            l += tmp[j][1]
            j += 1
            if j == len(tmp):
                break

l = len(tmp)

j = 0
k = 0

for i in range(n):
    if i == tmp[j][0]:
        print(ans[j][1]+tmp[j][1]*l - k*l)
        l -= 1
        k = tmp[j][1]
        if j < len(tmp)-1:
            j += 1
    else:
        print(0)

Submission status: Wrong Answer

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

ans = [0]*n

tmp = []
m = 0

for i in range(n):
    if m < a[i]:
        tmp.append([i,a[i]])
        m = a[i]
    else:
        j = 0
        k = 0
        while tmp[j][1] <= a[i]:
            k += tmp[j][1]
            ans[j] += k
            k = -tmp[j][1]
            j +=1
            if j == len(tmp):
                break

l = len(tmp)

j = 0
k = 0

for i in range(n):
    if i == tmp[j][0]:
        print(ans[i]+tmp[j][1]*l - k*l)
        l -= 1
        k = tmp[j][1]
        if j < len(tmp)-1:
            j += 1
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

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

nums = sorted(set(A), reverse = True) # desc
nums.append(0)
next_num = {x:y for x,y in zip(nums[:-1], nums[1:])}
L = len(nums)
a_to_i = {x:i for i,x in enumerate(nums,1)} # 1 to L

tasks = set()
x = 0
for i,a in enumerate(A):
    if A[i] > x:
        tasks.add(i)
        x = a

def BIT_update(tree, x):
    while x <= L:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree, x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

answer = [0] * N
tree = [0] * (L+1)

for i,x in list(enumerate(A))[::-1]:
    j = a_to_i[x]
    BIT_update(tree,j)
    if i in tasks:
        answer[i] = BIT_sum(tree,j) * (x - next_num[x])

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

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

N

A

nums = sorted(set(A), reverse = True) # desc
nums.append(0)
next_num = {x:y for x,y in zip(nums[:-1], nums[1:])}
L = len(nums)
a_to_i = {x:i for i,x in enumerate(nums,1)} # 1 to L

tasks = set()
x = 0
for i,a in enumerate(A):
    if A[i] > x:
        tasks.add(i)
    x = a

def BIT_update(tree, x):
    while x <= L:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree, x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

answer = [0] * N
tree = [0] * (L+1)

for i,x in list(enumerate(A))[::-1]:
    j = a_to_i[x]
    BIT_update(tree,j)
    if i in tasks:
        answer[i] = BIT_sum(tree,j) * (x - next_num[x])

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

    def suma(self, i, j):  # i,i+1,..j sum
        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
#print(ndd,dd)
visit=[0]*N
visit[0]=1
s=A[0]
for i in range(1,N):
    if s<A[i]:
        s=A[i]
        visit[i]=1
BITI=BIT(N+1)
l=dd[max(A)]
num=sum(A)
T=[0]*N
for i in range(N-1,-1,-1):
    BITI.add(dd[A[i]],1)
    if l==dd[A[0]]:
        break
    if dd[A[i]]==l and visit[i]==1:
        T[i]=BITI.suma(l,N+1)*(ndd[l]-ndd[l-1])
        l-=1
#print(visit)
x=num-sum(T)
T[0]=x
for t in T:
    print(t)