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

Solution (Python):
from functools import cmp_to_key

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

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

ans = [0] * n
g = group(a)
g.append([0, 0, 0])
for c, n in zip(g[:-1], g[1:]):
    ans[c[1]] += (c[0] - n[0]) * c[2]
    n[1] = min(c[1], n[1])
    n[2] += c[2]

[print(a) for a in ans]

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

Solution (Python):
from collections import Counter
N = int(input())
S = list(map(int,input().split()))
T = []
for i in range(N):
    T.append((i,S[i]))
U = sorted(T,key=lambda x:x[1], reverse=True)

Ans = [0]*N
c,v = 0,10**10

for i in range(N-1):
    c+=1
    v = min(v,U[i][0])
    if U[i][1]==U[i+1][1]:
        continue
    else:
        Ans[v] += (U[i][1] - U[i+1][1])*c
else:
    Ans[0] = 0
    Ans[0] = sum(S) - sum(Ans)

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

Solution (Python):
from collections import defaultdict

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

dic = defaultdict(lambda:(N,0))
for i,a in enumerate(src):
    m,n = dic[a]
    dic[a] = (min(m,i), n+1)
order = sorted(list(dic.items()))

hist = [0] * N
while True:
    a1, (m1, n1) = order.pop()
    if not order:
        hist[m1] += n1 * a1
        break
    a2, (m2, n2) = order[-1]
    hist[m1] += n1 * (a1-a2)
    order[-1] = (a2, (min(m1,m2), n1+n2))

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

Solution (Python):
n = int(input())
lis = list(map(int, input().split()))

key = lis[0]
num = [0]
li = [key]
for i in range(1,n):
	if lis[i] > key:
		key = lis[i]
		num.append(i)
		li.append(key)

m = len(li)
nu = [li[0]]+[li[i+1]-li[i] for i in range(m-1)]

he = [0]*m
cou = [0]*m

from bisect import bisect_left

for k in lis:
	sen = bisect_left(li,k)
	cou[sen] += k -li[sen]
	he[sen] += 1

key = 0
for i in reversed(range(m)):
	key += he[i]
	he[i] = key

for i in range(m):
	cou[i] += he[i]*nu[i]

ans = [0]*n
for i,c in zip(num,cou):
	ans[i] = c

for r in ans:
	print(r)

Solution (Python):
N = int(raw_input())
V = map(int, raw_input().split(' '))

sorted_V = [N-i-1 for i in range(N)]

sorted_V.sort(reverse=True,key=lambda x: V[x])
lowest = N

uses = [0 for i in range(N)]

last = V[sorted_V[0]]

for ind, val in enumerate(sorted_V):
	if ind != N - 1 and V[sorted_V[ind]] == V[sorted_V[ind + 1]]:
		continue

	lowest = min(lowest, val)
	spots = ind + 1

	if ind == N - 1:
		individual_removals = last
		last = 0
	else:
		individual_removals = last - V[sorted_V[ind + 1]]
		last = V[sorted_V[ind + 1]]

	full_removals = individual_removals * spots
	uses[lowest] += full_removals

for i in uses:
	print i

Solution (Python):
from collections import defaultdict

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

Solution (Python):
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=[]
d=defaultdict(int)
li=set([])
now=0
for i in xrange(n):
    if now<a[i]:
        now=a[i]
        check.append(i)
    d[a[i]]+=1
    li.add(a[i])
li=sorted(list(li))
b=[0]*(n+5)
i=0
idx=dict()
for key in li:
    b[i]=d[key]
    idx[key]=i
    i+=1
ans=[0]*(n+1)
for i in xrange(len(check)-2,-1,-1):
    cnt=0
    for j in xrange(idx[a[check[i]]]+1,idx[a[check[i+1]]]+1):
        ans[check[i+1]]+=b[j]*(li[j]-a[check[i]])
        cnt+=b[j]
    b[idx[a[check[i]]]]+=cnt
for i in xrange(1,n):
    if a[0]<a[i]:
        a[i]=a[0]
ans[0]=sum(a)
for i in xrange(n):
    print ans[i]

Solution (Python):
n = int(input())
an = list(map(int, input().split()))
sa = sorted(((a, i) for i, a in enumerate(an)), reverse=True)
sa.append((0, 0))

result = [0] * n
prev_a, min_i = sa[0]
for j, (a, i) in enumerate(sa[1:]):
    result[min_i] += (j + 1) * (prev_a - a)
    min_i = min(min_i, i)
    prev_a = a

for cnt in result:
    print(cnt)

Solution (Python):


n_mou = int(input())
l_mou = list(map(int, input().split()))
l_mou_ind = [[l_mou[i], i] for i in range(n_mou)]
l_mou_ind.sort()

l_ans = [0 for i in range(n_mou)]

l_ans[0] = l_mou_ind[0][0] * n_mou
min_index = l_mou_ind[-1][1]
for i in range(n_mou - 1, 0, -1):
    min_index = min(min_index, l_mou_ind[i][1])
    if l_mou_ind[i - 1][0] != l_mou_ind[i][0]:
        l_ans[min_index] += (l_mou_ind[i][0] - l_mou_ind[i - 1][0]) * (n_mou - i)

for i in range(n_mou):
    print(l_ans[i])

Solution (Python):

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])
min_a_i = float('inf')
for i,p in enumerate(a[:-1]):
    min_a_i = min(min_a_i, a[i][1])
    if not p[0] == a[i+1][0]:
        q = p[0] - a[i+1][0]
        s[min_a_i-1] += (i+1)*q

for t in s:
    print(t)

Solution (Python):
def binary_search(item, values):
  top = 0
  bottom = len(values) - 1
  length = bottom - top + 1
  middle = top + (length // 2)
  while length >= 1:
    middle_item = values[middle][1]
    if middle_item == item:
      break
    if middle_item < item:
      top = middle + 1
    else:
      bottom = middle - 1
    length = bottom - top + 1
    middle = top + (length // 2)
  if middle <= (len(values) - 1):
    return middle
  else:
    return -1

n = int(raw_input().rstrip("\n"))
piles = map(int, raw_input().rstrip("\n").split(" "))

limits = [(-1, 0)]
from collections import defaultdict
counter = defaultdict(int)
gaps = defaultdict(int)
for i , count in enumerate(piles):
  position = binary_search(count, limits)
  if position == -1:
    limits.append((i, count))
    counter[i] += 1
  else:
    limit_index, limit = limits[position]
    counter[limit_index] += 1
    gaps[limit_index] -= limit - count
    
results = defaultdict(int)

total = 0
for position in xrange(len(limits)-1,0,-1):
  limit_index, limit = limits[position]
  
  results[limit_index] = (total + counter[limit_index]) * (limit - limits[position -1][1]) + gaps[limit_index]
  total += counter[limit_index]

for i in xrange(n):
  print results[i]

Solution (Python):



def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

n = int(input())
a = readln()
c = sorted([[-a[i],i]for i in range(0,n)])
ans = [0 for i in range(0,n)]
front = c[0][1]
for i in range(1,n):
    ans[front] = ans[front] + i * (c[i][0] - c[i-1][0])
    if front > c[i][1]:
        front = c[i][1]

ans[front] = ans[front] + n * (-c[n-1][0])
for a in ans:
    print(a)

Solution (Python):
from bisect import bisect
n = input()
A = map(int, raw_input().split())
st = [(0, 0)]

part = [0]*(n+1)
block = [0]*(n+1)

for i in xrange(n):
    if st[-1][0] < A[i]:
        st.append((A[i], i))
    idx = bisect(st, (A[i], -1))
    part[idx] += A[i] - st[idx-1][0]
    block[idx-1] += 1
ans = [0]*n
tmp = 0
for i in range(1, len(st))[::-1]:
    tmp += block[i]
    ans[st[i][1]] = tmp*(st[i][0] - st[i-1][0]) + part[i]
print "\n".join(map(str, ans))

Solution (Python):
def nibutan(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 = nibutan(th, a)
        if j - 1 >= 0:
            num_th[j - 1] += 1
        rem[j] += a - th[j]

for i in range(len(num_th) - 1, 0, -1):
    num_th[i - 1] += num_th[i]

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

Solution (Python):

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)

Solution (Python):
def solve():
    n = int(input())
    work_array = [[a, b] for a, b in zip([int(i) for i in input().split()], [j for j in range(0, n)])]
    ans_list = [0] * n
    work_array.sort(reverse=True)

    last_num = work_array[0][0]
    min_index = work_array[0][1]
    for counter in range(n):
        current_num = work_array[counter][0]
        if last_num != current_num:
            ans_list[min_index] += counter * (last_num - current_num)
            last_num = current_num
        min_index = min(min_index, work_array[counter][1])

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

if __name__=="__main__":
    solve()

Solution (Python):
n=int(raw_input())
a=[]
for i,j in enumerate(map(int,raw_input().split())):
    a.append([j,i])
a.sort(reverse=True)
now=0
nx=0
ans=[0]*n
cnt=0
idx=10**6
while now<n:
    while nx<n and a[now][0]==a[nx][0]:
        idx=min(idx,a[nx][1])
        cnt+=1
        nx+=1
    if nx==n:
        ans[idx]+=cnt*a[now][0]
    else:
        ans[idx]+=(a[now][0]-a[nx][0])*cnt
    now=nx
for i in xrange(n):
    print ans[i]

Solution (Python):
from collections import defaultdict, Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)


values = reversed(sorted(set(a)))
s = 0
m = 0
above = dict()
n_above = dict()
for v in values:
    above[v] = s
    n_above[v] = m
    s += c[v] * v
    m += c[v]
above[0] = s
n_above[0] = m


m = 0
u = [0]
for v in a:
    if v > m:
        u.append(v)
        m = v

r = defaultdict(int)
last = 0
for j, v in enumerate(u):
    r[v] = last - (above[v] - n_above[v] * v)
    last = above[v] - n_above[v] * v



m = 0
for v in a:
    if v > m:
        print(r[v])
        m = v
    else:
        print(0)

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












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

ans = [0] * n
min_a_i = float('inf')
for i in range(n):
    min_a_i = min(min_a_i, ai[i][1])
    ans[min_a_i] += (ai[i][0] - ai[i+1][0]) * (i+1)

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

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
b = [ (a[i], i, 0) for i in range(N)]

b.sort(key= lambda x: (-x[0], x[1]))



mini = 0

for i in range(N-1):
    if b[i][1] < b[mini][1]:
        mini = i

    b[mini] = b[mini][0], b[mini][1], b[mini][2] + (b[i][0]-b[i+1][0])*(i+1)

if b[N-1][1] < b[mini][1]:
    mini = N-1
b[mini] = b[mini][0], b[mini][1], b[mini][2] + (b[N-1][0])*N

b.sort(key = lambda x: x[1])

for x in b:
    print(x[2])

Solution (Python):
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, m])
        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
        mi[j][1] += a[i] - mi[j][4]

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

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

Solution (Python):
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]

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

t = A[0]
indices = [0]
seq = [t]
for i in range(1,N):
  if A[i] > t:
    t = A[i]
    indices.append(i)
    seq.append(t)

M = len(seq)
delta = [seq[0]]+[seq[i+1]-seq[i] for i in range(M-1)]

temp = [0]*M
count = [0]*M


from bisect import bisect_left
for a in A:
  p = bisect_left(seq, a)
  count[p] += a - seq[p]
  temp[p] += 1

t = 0
for i in reversed(range(M)):
  t += temp[i]
  temp[i] = t

for i in range(M):
  count[i] += temp[i]*delta[i]

result = [0]*N
for i,c in zip(indices,count):
  result[i] = c

for r in result:
  print(r)

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

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


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

print(main())

Solution (Python):
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

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

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

N = read()
a = reads()

b = [(-a[i], i) for i in range(N)]
b.sort()
b.append((0, -1))


result = [0] * N

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


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