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: Runtime Error

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
    cnt+=1
ans[0]=sum(A)-sum(ans)

for u in ans:
    print(u)

Submission status: Runtime Error

Solution code:
import collections
import heapq
n=int(input())
A=[int(i) for i in input().split()]
Ans=[0]*n
M=[0]#自分より前の最大値をメモ。これ以下だと現れない
for i in range(n):
  M.append(max(M[-1],A[i]))
D=collections.defaultdict(int)
H=[]
for i in range(n):
  j=n-1-i
  if A[j]<=M[j]:
    heapq.heappush(H,-A[j])#出現しないインデックスの数を管理。大きいほうから取り出す。
  else:
    Ans[j]=(A[j]-M[j])*(D[A[j]]+1)#自分より前の最大値と自分の差かける自分自身と同じ数のこれまでの出現回数
    D[M[j]]+=D[A[j]]+1#自分自身より後ろの自分と同じ数全てを自分より前の最大値まで減らすことで増える分
    ct=0
    while H:#自分より後ろで自分より小さいが、自分の前の最大値より大きいものを全て見る
      a=heapq.heappop(H)
      a=-a
      if a<=M[j]:
        heapq.heappush(H,-a)
        break
      else:
        Ans[j]+=a-M[j]
        D[M[j]]+=1

for a in Ans:
  print(Ans)

Submission status: Runtime Error

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))
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: Runtime Error

Solution code:
n,a=open(0)
*a,=map(int,a.split())
c,d={},{}
m=0
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]]=(i-j)*c[i]
  c[j]+=c[i]
a[d[j]]=j*c[j]
print(*a)

Submission status: Runtime Error

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, a)
    ans[now] += j * (now - A[j][0])

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

Submission status: Runtime Error

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*min(b)
for i in range(N):
    print(ans[i+1])

Submission status: Runtime Error

Solution code:
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
typedef pair<lint,int>pli;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

int main(){
  int n;
  cin>>n;
  vector<lint>a(n);
  rep(i,n)cin>>a[i];
  vector<pli>b(n);
  rep(i,n)b[i]=pli(a[i],i);
  sort(b.rbegin(),b.rend());
  vector<lint>ans(n);
  int mi=n;
  rep(i,n){
    if(i==n-1||b[i].first!=b[i+1].first){
      mi=min(b[i].second,mi);
      lint diff=b[i].first-(i==n-1?0:b[i+1].first);
      ans[mi]+=diff*(i+1);
    }
  }
  rep(i,n)cout<<ans[i]<<endl;
}

Submission status: Runtime Error

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] += U[i+1][1]

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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)
u = []
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
        u.extend([min(y)]*(i+1)*q)

for t in s:
    print(t)

Submission status: Runtime Error

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 = []
b = []
a.append([0,0])
for i,p in enumerate(a[:-1]):
    if not p[0] == a[i+1][0]:
        q = a[i][0] - a[i+1][0]
        y = [z[1] for z in a[:i+1]]
        s.extend([min(y)]*(i+1)*q)

for i in xrange(1,int(n)+1):
    print(s.count(i))

Submission status: Runtime Error

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 = []
b = []
a.append([0,0])
while (True):
    if a[-2][0]==0:break
    a.sort(key=itemgetter(1),reverse=True)
    a.sort(key=itemgetter(0),reverse=True)
    b=[]
    for i,p in enumerate(a[:-1]):
        if not p[0] == a[i+1][0]:
            q = p[0] - a[i+1][0]
            s.extend([p[1]]*(i+1)*q)
            for j in range(i):
                a[j][0] = a[i+1][0]
            a[i][0] = a[i+1][0]
            break
        else:
            pass
for i in xrange(1,int(n)+1):
    print(s.count(i))

Submission status: Runtime Error

Solution code:

def BS(th, a):
    top = len(th)
    btm = 0

    while top > btm:
        mid = (top + btm)//2
        if th[mid] <= a < th[mid + 1]:
            return mid
        elif a <= th[mid]:
            top = mid
        else:
            btm = mid

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

th = [0]
num_th = []
rem = []
max_i = 0
nonzeros = dict()

for i, a in enumerate(A):
    if a > th[-1]:
        th.append(a)
        num_th.append(1)
        rem.append(0)
        nonzeros[i] = max_i
        max_i += 1
    else:
        j = BS(th, a)
        if j - 1 >= 0:
            num_th[j - 1] += 1
        rem[j] += a - th[j]

for i in range(len(num_th) - 1, 0, -1):
    num_th[i - 1] += num_th[i]
'''
print(th)
print(num_th)
print(rem)
'''
for i in range(N):
    if i in nonzeros:
        ans = (th[nonzeros[i] + 1] - th[nonzeros[i]])*num_th[nonzeros[i]] + rem[nonzeros[i]]
        print(ans)
    else:
        print(0)