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

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)
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 dd[A[i]]==l:
        T[i]=BITI.suma(l,N+1)*(ndd[l]-ndd[l-1])
        l-=1
    if l==1:
        break
x=num-sum(T)
T[0]=x
for t in T:
    print(t)

Submission status: Wrong Answer

Solution code:
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
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 = []
for i in range(N):
    b.append([a[i], i+1])
b.sort(reverse = True)
ans = [0]*(N+1)
if b[0][1] == 1:
    ans[1] = sum(a)
else:

    for i in range(N):
        if b[i][1] == 1:
            ans[1] = sum(a)-sum(ans)
            break
        if b[i+1][0] - b[i][0] < 0:
            ans[b[i][1]] = (b[i][0] - b[i+1][0])*(i+1)

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

Submission status: Wrong Answer

Solution code:
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def b_sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
a = list(map(int, input().split()))
c = sorted(list(set(a)))
num = 2
d = dict()
for i in range(len(c)):
	d[c[i]] = i+1
e = [d[a[i]] for i in range(n)]
#print(a)
b = BIT(n+2)
greater = [0 for _ in range(n)]
for i in range(n-1, -1, -1):
	greater[i] = n-i - b.b_sum(e[i] - 1)
	b.b_add(e[i], 1)
#print(greater)
M = max(a)
cur = 0
s = 0
for i in range(n):
	if a[i] > cur:
		print(greater[i] * (a[i] - cur))
		cur = a[i]
	else:
		print(0)

Submission status: Wrong Answer

Solution code:
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def b_sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
a = list(map(int, input().split()))
c = sorted(list(set(a)))
num = 2
d = dict()
for i in range(len(c)):
	d[c[i]] = i+1
e = [d[a[i]] for i in range(n)]
#print(a)
b = BIT(n+2)
greater = [0 for _ in range(n)]
for i in range(n-1, -1, -1):
	greater[i] = n-i - b.b_sum(e[i] - 1)
	b.b_add(e[i], 1)
print(greater)
M = max(a)
cur = 0
s = 0
for i in range(n):
	if a[i] > cur:
		print(greater[i] * (a[i] - cur))
		cur = a[i]
	else:
		print(0)

Submission status: Wrong Answer

Solution code:
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def b_sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
a = list(map(int, input().split()))
su = sum(a)
c = sorted(list(set(a)))
num = 2
d = dict()
for i in range(len(c)):
	d[c[i]] = i+1
e = [d[a[i]] for i in range(n)]
#print(a)
b = BIT(n+2)
greater = [0 for _ in range(n)]
for i in range(n-1, -1, -1):
	greater[i] = n-i - b.b_sum(e[i] - 1)
	b.b_add(e[i], 1)
#print(greater)
M = max(a)
cur = 0
s = 0
for i in range(n):
	if cur == M:
		print(0)
	elif a[i] > cur:
		print(greater[i] + a[i] - cur - 1)
		cur = a[i]
	else:
		print(0)

Submission status: Wrong Answer

Solution code:
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def b_sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
a = list(map(int, input().split()))
su = sum(a)
c = sorted(list(set(a)))
num = 2
d = dict()
for i in range(len(c)):
	d[c[i]] = i+1
a = [d[a[i]] for i in range(n)]
#print(a)
b = BIT(n+2)
greater = [0 for _ in range(n)]
for i in range(n-1, -1, -1):
	greater[i] = n-i - b.b_sum(a[i] - 1)
	b.b_add(a[i], 1)
#print(greater)
M = max(a)
cur = 0
s = 0
for i in range(n):
	if cur == M:
		print(0)
	elif a[i] == M:
		print(su - s)
		s = su
		cur = M
	elif a[i] > cur:
		print(greater[i])
		s += greater[i]
		cur = a[i]
	else:
		print(0)

Submission status: Wrong Answer

Solution code:
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def b_sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
a = list(map(int, input().split()))
su = sum(a)
c = sorted(list(set(a)))
num = 2
d = dict()
for i in range(len(c)):
	d[c[i]] = i+1
a = [d[a[i]] for i in range(n)]
#print(a)
b = BIT(n+2)
greater = [0 for _ in range(n)]
for i in range(n-1, -1, -1):
	greater[i] = n-i - b.b_sum(a[i] - 1)
	b.b_add(a[i], 1)
#print(greater)
M = max(a)
cur = 0
s = 0
for i in range(n):
	if cur == M:
		print(0)
	elif a[i] == M:
		print(su - s)
		s = su
	elif a[i] > cur:
		print(greater[i])
		s += greater[i]
		cur = a[i]
	else:
		print(0)

Submission status: Wrong Answer

Solution code:
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
    pma = a
    ofs = a
    print(s)

Submission status: Wrong Answer

Solution code:
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
for i in range(len(c)-1):
    x = (c[i][0]-c[i+1][0])*c[i][2]
    ans[c[i][1]] = x
    s += x
ans[c[-1][1]] = sum(a)-s

for x in ans:
    print(x)

Submission status: Wrong Answer

Solution code:
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] * len(a)
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]

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

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

def cmp(x, y):
    return x[1] - y[1]

def group(a):
    d = {}
    for i, x in enumerate(a):
        d.setdefault(x, []).append(i)
    return list(sorted(d.items(), key=cmp_to_key(lambda x, y: x[0] - y[0]), reverse=True))

ans = [0] * len(a)
g = group(a)
g.append((0, []))
for c, n in zip(g[:-1], g[1:]):
    ans[c[1][0]] = (c[0] - n[0]) * len(c[1])
    if n[1] and n[1][0] < c[1][0]:
        tmp = n[1].copy()
        n[1].clear()
        n[1].extend(tmp + c[1])
    else:
        tmp = n[1].copy()
        n[1].clear()
        n[1].extend(c[1] + tmp)

[print(a) for a in ans]

Submission status: Wrong Answer

Solution code:
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)
B = [0 for i in range(N)]
B[0] = N
num = S[0][1]
for i in range(1, N):
  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)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

    def sum(self,idx):
        ret=0
        while idx>0:
            ret+=self.node[idx]
            idx-=idx&(-idx)
        return ret

    def add(self,idx,x):
        while idx<=self.size:
            self.node[idx]+=x
            idx+=idx&(-idx)

n=int(raw_input())
a=map(int,raw_input().split())
check=[0]
d=defaultdict(int)
li=set([])
now=0
for i in xrange(n):
    if now<a[i]:
        now=a[i]
        check.append(i+1)
    d[a[i]]+=1
    li.add(a[i])
li=sorted(list(li))
bit=BIT(n)
i=1
idx=dict()
for key in li:
    bit.add(i,d[key])
    idx[key]=i
    i+=1
ans=[0]*(n+1)
for i in xrange(len(check)-1):
    if i==0:
        ans[check[i+1]]=(a[check[i+1]-1])*(bit.sum(n)-bit.sum(0))
    else:
        ans[check[i+1]]=(a[check[i+1]-1]-a[check[i]-1])*(bit.sum(n)-bit.sum(idx[a[check[i+1]-1]]-1))
for i in xrange(1,n+1):
    print ans[i]

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
a = np.array(list(map(int, input().split(" "))))

s = []
while 1:
    max_idx_a = np.argmax(a)
    b = a[::-1]
    max_idx_b = len(b) - np.argmax(b) - 1
    if a[max_idx_a] < 1:
        break
    else:
        s.append(max_idx_a)
        a[max_idx_b] -= 1

counter = [0 for i in range(N)]
for i in range(len(s)):
    counter[s[i]] += 1

print(counter)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
from operator import itemgetter
n = int(raw_input())
a = [[int(k),i+1] for i,k in enumerate(raw_input().split())]
a.sort(key=itemgetter(0),reverse=True)
s=[0]*n
a.append([0,0])
for i,p in enumerate(a[:-1]):
    if not p[0] == a[i+1][0]:
        q = p[0] - a[i+1][0]
        y = [z[1] for z in a[:i+1]]
        s[min(y)-1] = (i+1)*q
for t in s:
    print(t)

Submission status: Wrong Answer

Solution code:
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]
    counter = 0
    same_numbers = []
    while counter < n:
        current_num = work_array[counter][0]
        if last_num != current_num:
            same_numbers.sort()
            ans_list[int(same_numbers[0])] += counter * (last_num - current_num)
            last_num = current_num
            same_numbers = []
        same_numbers.append(str(work_array[counter][1]))
        counter += 1

    same_numbers.sort()
    ans_list[int(same_numbers[0])] += counter * last_num
    print("\n".join([str(c) for c in ans_list]))

if __name__=="__main__":
    solve()

Submission status: Wrong Answer

Solution code:
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(key=lambda x:(x[0], x[1]), reverse=True)

    last_num = work_array[0][0]
    same_number_count = 1
    counter = 1
    while counter < n:
        current_num = work_array[counter][0]
        if last_num != current_num:
            ans_list[work_array[counter - 1][1]] += \
                counter * (last_num - current_num)

            same_number_count = 0
            last_num = current_num
        counter += 1
        same_number_count += 1

    ans_list[work_array[counter - 1][1]] += counter * last_num
    print("\n".join([str(c) for c in ans_list]))

if __name__=="__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())
ai = zip(a,range(n))
ai.sort()

ans = [0] * n
ai = [(0,0)] + ai
for i in range(1,n+1):
    a,a_i = ai[i]
    ans[a_i] += (ai[i][0]-ai[i-1][0]) * (n-i+1)

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

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())
ai = zip(a,range(n))
ai.sort()

ans = [0] * n
prev = 0
for i in range(n):
    a,a_i = ai[i]
    ans[a_i] += (a-prev) * (n-i)
    prev = a

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy
if __name__=="__main__":
    N = int(input())
    a = np.array(list(map(int, input().split()))).astype(np.int32)
    ans = np.zeros(N).astype(np.int32)
    for i in range(N):
        max_first = np.max(a)
        index1 = np.where(a == max_first)
        if(index1[0][0] == 0):
            break
        max_second = np.max(a[0:index1[0][0]])
        index2 = np.where(a == max_second)
        ans[index1[0][0]] = np.sum(a[a > max_second] - max_second)
        a[a > max_second] = max_second
    ans[0] = np.sum(a)
    for i in ans:
        print(i)

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())
ai = zip(a,range(n))
# ai.sort()

# ans = [0] * n
# prev = 0
# for i in range(n):
#     a,a_i = ai[i]
#     ans[a_i] = (a-prev) * (n-i)
#     prev = a

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

ai.sort()
ai = ai[::-1]
ai.append((0,0)) # dummy

ans = [0] * n
for i in range(n):
    # a,a_i = ai[i]
    ans[ai[i][1]] = (ai[i][0] - ai[i+1][0]) * (i+1)

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

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())
ai = zip(a,range(n))
ai.sort()

ans = [0] * n
prev = 0
for i in range(n):
    a,a_i = ai[i]
    ans[a_i] = (a-prev) * (n-i)
    prev = a

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy
if __name__=="__main__":
    N = int(input())
    a = np.array(list(map(int, input().split()))).astype(np.int32)
    b = copy.copy(a)
    ans = np.zeros(N).astype(np.int32)
    for i in range(N):
        max_first = np.max(a)
        index1 = np.where(a == max_first)
        if(index1[0][0] == 0):
            break
        max_second = np.max(a[0:index1[0][0]])
        print(max_first, max_second)
        index2 = np.where(a == max_second)
        ans[index1[0][0]] = np.sum(a[a > max_second] - max_second)
        a[a > max_second] = max_second
    ans[0] = np.sum(a)
    for i in ans:
        print(i)

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())
ai = zip(a,range(1,n+1))
# print ai
ai.sort()
# print ai

ans = [0] * (n+1)

oldh = 0
h  = 0
hi = 0
w  = 0
for i in range(n):
    a,a_i = ai[i]
    if h != a:
        ans[hi] = (h-oldh) * w
        oldh = h
        h = a
        hi = a_i
        w = n-i

ans[hi] = (h-oldh) * w

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

Submission status: Wrong Answer

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

ans = {}

while a:
    f = max(a)
    arg_f = a.index(f)
    ans[arg_f+1] = 0
    b = [i for i in a if i != f]
    if b:
        s = max(b)
        for i in [arg_f+i for i in range(n-arg_f)]:
            if a[i] == f:
                ans[arg_f+1] += f - s
                a[i] = s
    else:
        ans[arg_f+1] += sum(a)
        a = []

for i in range(n):
    if i+1 in ans:
        print ans[i+1]
    else:
        print 0

Submission status: Wrong Answer

Solution code:
from sys import stdin
n = int(stdin.readline())
ans = [0] * (n+2)
a = [0] + map(int,stdin.readline().split())
b = []
for i in xrange(1,n+1):
    b.append((a[i],i))
b.sort()
b.reverse()
first = {}
co = {}
for x,y in b:
    if x not in first:
        first[x] = y
    else:
        first[x] = min(first[x],y)
first[0] = 0        
m = set(a)
for i in a:
    co[i] = co.get(i,0) + 1
   
m = list(m)
m.sort()
m.reverse()
l = len(m)

for i in xrange(l-1):
    cur = m[i]
    fir = co[cur]
    mi = first[cur]
    sec = m[i+1]
    ans[mi]=(m[i]-m[i+1])*fir
    co[sec] += fir
    first[sec] = min(first[sec],first[cur])
for i in xrange(1,n+1):
    print ans[i]

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
a = [int(x) for x in raw_input().split()]

mi = []
l = 0
m = 0

for i in xrange(n):
    if a[i] > m:
        mi.append([i, a[i] - m, a[i], 1])
        l += 1
        m = a[i]
    else:
        jl = 0
        ju = l
        while jl < ju:
            mid = (jl + ju) / 2
            if mi[mid][2] < a[i]:
                jl = mid + 1
            else:
                ju = mid
        j = jl
        mi[j][3] += 1

s = 0
for i in xrange(l - 1, -1, -1):
    s += mi[i][3]
    mi[i][3] = s

j = 0
for i in xrange(n):
    if j >= l:
        print 0
        continue
    ii, d, ai, ni = mi[j]
    if ii == i:
        print d * ni
        j += 1
    else:
        print 0

Submission status: Wrong Answer

Solution code:
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
    t = [b[0][1]]
    s = sum(a)
    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)
        r[bi] += ti
        s -= ti
    return '\n'.join(map(str, r))

print(main())

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()
ans = [0 for i in range(n)]
ans[0] = b[0][0] * n
pre = b[0][0]
for i in range(1, n):
    if b[i-1][0] != b[i][0]:
        ans[b[i][1]] = (b[i][0] - pre) * (n-i)
        pre = b[i][0]
for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
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))
# print(b)

result = [0] * N

j = 0
for i in range(1, N+1):
  if b[j][0] != b[i][0]:
    # print(j, i, (b[i][0] - b[j][0]))
    result[b[j][1]] = (b[i][0] - b[j][0]) * i
    j = i

# print(" ".join(str(k) for k in result))
for i in range(N):
  print(result[i])

Submission status: Time Limit Exceeded

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)

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

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
        for j in range(max_+1,a[i]):
            ans[i] += (j-max_)*d[j]
        max_ = a[i]

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
from collections import Counter

N = int(stdin.readline())
a = list(map(int, stdin.readline().split()))

l = len(a)
Result = [0] * l
while sum(a) != 0:
    max_arr = max(a)
    count = 0
    for x in range(l):
        if a[x] == max_arr:
            if a.count(max_arr) > 1:
                if count == 1:
                    a[x] -= 1
                    Result[i] += 1
                    break
                else:
                    count += 1
                    i = x
            else:
                a[x] -= 1
                Result[x] += 1
                break
for i in range(l):
    stdout.write(str(Result[i]) + '\n')

Submission status: Time Limit Exceeded

Solution code:

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)):
	bisect.insort(com, a[top_list[i]])


for i in range(N - 1, top_list[-1], -1):
	bisect.insort(com, a[i])

stock = 0
#print(com, top_list, num_list)
for top in range(len(top_list) - 2, -1, -1):
	for i in range(top_list[top + 1] - 1, top_list[top], -1):
		#bisect.insort(com, a[i])
		com.append(a[i])
	com.sort()
	judge = 0
	total = stock*(a[top_list[top + 1]] - a[top_list[top]])
	#print(total, (a[top_list[top + 1]] - a[top_list[top]])*stock,  top)
	while judge == 0:
		x = com.pop()
		if x > a[top_list[top]]:
			total += x - a[top_list[top]]
			stock += 1
		else:
			bisect.insort(com, x)
			judge = 1
	num_list[top_list[top + 1]] = total
	#print(com, top_list, num_list, stock)


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

Submission status: Time Limit Exceeded

Solution code:

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)):
	bisect.insort(com, a[top_list[i]])


for i in range(N - 1, top_list[-1], -1):
	bisect.insort(com, a[i])

stock = 0
#print(com, top_list, num_list)
for top in range(len(top_list) - 2, -1, -1):
	for i in range(top_list[top + 1] - 1, top_list[top], -1):
		bisect.insort(com, a[i])
	judge = 0
	total = stock*(a[top_list[top + 1]] - a[top_list[top]])
	#print(total, (a[top_list[top + 1]] - a[top_list[top]])*stock,  top)
	while judge == 0:
		x = com.pop()
		if x > a[top_list[top]]:
			total += x - a[top_list[top]]
			stock += 1
		else:
			bisect.insort(com, x)
			judge = 1
	num_list[top_list[top + 1]] = total
	#print(com, top_list, num_list, stock)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

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

# 現在末尾に追加される山より若い山で，最も個数の大きいものが次の山になる
# 他の山を次の山の個数以下まで減らす

nextNumIndex = deque([0])

for i, a in enumerate(A[1:], start=1):
    if a > A[nextNumIndex[-1]]:
        nextNumIndex.append(i)

V = set()  # 大きい山
W = set(range(N))  # 小さい山
ansList = defaultdict(int)

while len(nextNumIndex) > 1:
    nowIndex = nextNumIndex.pop()
    nextIndex = nextNumIndex[-1]

    newW = set()
    cnt = len(V) * (A[nowIndex] - A[nextIndex])
    for w in W:
        if A[w] >= A[nextIndex]:
            V.add(w)
            cnt += A[w] - A[nextIndex]
        else:
            newW.add(w)
    W = newW
    ansList[nowIndex] = cnt

    if len(nextNumIndex) == 1:
        for i in range(N):
            A[i] = min(A[i], A[nextIndex])

ansList[0] = sum(A)

ans = []
for i in range(N):
    ans.append(ansList[i])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

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

# 現在末尾に追加される山より若い山で，最も個数の大きいものが次の山になる
# 他の山を次の山の個数以下まで減らす

nextNumIndex = deque([0])

for i, a in enumerate(A[1:], start=1):
    if a > A[nextNumIndex[-1]]:
        nextNumIndex.append(i)

ans = defaultdict(int)
while len(nextNumIndex) > 1:
    nowNum = nextNumIndex.pop()
    nextNum = nextNumIndex[-1]
    cnt = 0
    for i in range(nextNum, N):
        cnt += max(0, A[i] - A[nextNum])
        A[i] = min(A[i], A[nextNum])

    ans[nowNum] = cnt

ans[nextNumIndex.pop()] = sum(A)

out = []
for i in range(N):
    out.append(ans[i])
print(*out, sep='\n')

Submission status: Time Limit Exceeded

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

df = []
ans = [0]*n
m = 0

for i in range(n):
    if m < a[i]:
        df.append([i,a[i]-m])
        m = a[i]

    j = 0
    tmp = a[i]
    while tmp > 0:
        ans[df[j][0]] += min(tmp,df[j][1])
        tmp -= df[j][1]
        j += 1
        if j == len(df):
            break

j = 0

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

Submission status: Time Limit Exceeded

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

df = []
ans = []
m = 0

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

j = 0

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dic = defaultdict(lambda: [])
for i,a in enumerate(src):
    dic[a].append(i)
order = sorted(list(dic.items()))

hist = [0] * N
while True:
    a1,l1 = order.pop()
    if not order:
        hist[min(l1)] += len(l1) * a1
        break
    a2,l2 = order[-1]
    hist[min(l1)] += len(l1) * (a1-a2)
    l2 += l1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    N = int(raw_input())
    a = np.array(map(int, raw_input().split(' ')))
    s = [0 for i in range(N)]


    if N < 1 or N > 10**5:
        return 0
    if max(a) < 1 or max(a) > 10**9:
        return 0

    while max(a) != 0:
        x = np.where(a == a.max())[0]
        a[max(x)] -= 1
        s[min(x)] += 1

    for i in s:
        print i

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
n = int(raw_input())
a = [[int(k),i+1] for i,k in enumerate(raw_input().split())]
a.sort(reverse=True)
z = [l[1] for l in a]
s=[0]*n
a.append([0,0])
for i,p in enumerate(a[:-1]):
    if not p[0] == a[i+1][0]:
        q = p[0] - a[i+1][0]
        y = z[:i+1]
        s[min(y)-1] += (i+1)*q

for t in s:
    print(t)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
from operator import itemgetter
n = int(raw_input())
a = [[int(k),i+1] for i,k in enumerate(raw_input().split())]
a.sort(key=itemgetter(0),reverse=True)
s=[0]*n
a.append([0,0])
for i,p in enumerate(a[:-1]):
    if not p[0] == a[i+1][0]:
        q = p[0] - a[i+1][0]
        y = [z[1] for z in a[:i+1]]
        s[min(y)-1] += (i+1)*q

for t in s:
    print(t)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
n = int(raw_input())
a = map(int,raw_input().split())

s = []

while True:
    if not any(a):
        break
    ma = max(a)
    x = a.index(ma)
    s.append(x+1)
    b = [i for i,x in enumerate(a) if x>=1 and x == ma]
    a[b[-1]] -= 1
for i in xrange(1,n+1):
    print(s.count(i))