One very well-known internet resource site (let's call it X) has come up with a New Year adventure. Specifically, they decided to give ratings to all visitors.

There are n users on the site, for each user we know the rating value he wants to get as a New Year Present. We know that user i wants to get at least a_{i} rating units as a present.

The X site is administered by very creative and thrifty people. On the one hand, they want to give distinct ratings and on the other hand, the total sum of the ratings in the present must be as small as possible.

Help site X cope with the challenging task of rating distribution. Find the optimal distribution.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 3·10^5) — the number of users on the site. The next line contains integer sequence a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print a sequence of integers b_1, b_2, ..., b_{n}. Number b_{i} means that user i gets b_{i} of rating as a present. The printed sequence must meet the problem conditions. 

If there are multiple optimal solutions, print any of them.


-----Examples-----
Input
3
5 1 1

Output
5 1 2

Input
1
1000000000

Output
1000000000

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Greedy algorithms


Solutions:
import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def get_ints():
	return map(int, sys.stdin.readline().split())
n = int(input())
arr1 = list(get_ints())
arr = []
for i in range(n):
	arr.append([arr1[i], i])
arr = sorted(arr, key=lambda x: x[0])
prev = arr[0][0]
ans = [0] * n
ans[arr[0][1]] = prev
for i in range(1, n):
	if prev < arr[i][0]:
		ans[arr[i][1]] = arr[i][0]
		prev = arr[i][0]
	elif prev == arr[i][0]:
		prev += 1
		ans[arr[i][1]] = prev
	else:
		prev += 1
		ans[arr[i][1]] = prev
print(*ans)


def main():
	n = int(input())
	aa = list(map(int, input().split()))
	idx = sorted(list(range(n)), key=aa.__getitem__)
	b = 0
	for i in idx:
		aa[i] = b = max(b + 1, aa[i])
	print(' '.join(map(str, aa)))

def __starting_point():
	main()
__starting_point()


import sys
n = int(sys.stdin.readline())
l = [int(x) for x in sys.stdin.readline().split(' ')]
ind = sorted(range(len(l)), key=lambda x: l[x])
h = l[ind[0]] - 1
for i in ind:
	if l[i] <= h:
		l[i] = h + 1
		h += 1
	else:
		h = l[i]
print(' '.join([str(x) for x in l]))


import sys
n = int(input())
a = list(map(int, sys.stdin.read().split()))
g = sorted(range(n), key=lambda x: a[x])
for i in range(1, n):
	if a[g[i]] <= a[g[i - 1]]:
		a[g[i]] = a[g[i - 1]] + 1
print(' '.join(map(str, a)))


i = int(input())
rat = list(map(int, input().split(' ')))
ratp = sorted(range(i), key=lambda x: rat[x])
final = [-1] * i
start = 0
for i in ratp:
	if start + 1 >= rat[i]:
		start = start + 1
	else:
		start = rat[i]
	final[i] = start
print(' '.join([str(x) for x in final]))


n = int(input())
l = list(map(int, input().split(' ')))
idxs = sorted(range(n), key=lambda x: l[x])
for i in range(1, n):
	if l[idxs[i]] <= l[idxs[i - 1]]:
		l[idxs[i]] = l[idxs[i - 1]] + 1
print(' '.join(map(str, l)))


n = int(input())
a = [*map(int, input().split())]
b = sorted([(i, a[i]) for i in range(n)], key=lambda x: x[1])
current = 0
for i in b:
	if current < i[1]:
		current = i[1]
		a[i[0]] = str(a[i[0]])
	else:
		current += 1
		a[i[0]] = str(current)
print(' '.join(a))


n = int(input())
t = 0
(*l,) = map(int, input().split())
a = l[:]
s = sorted(range(n), key=lambda x: l[x])
for i in s:
	if l[i] > t:
		t = l[i]
		a[i] = str(t)
	else:
		t += 1
		a[i] = str(t)
print(' '.join(a))


n = int(input().strip())
a = list(map(int, input().strip().split()))
t = sorted(range(n), key=lambda x: a[x])
cur = -1
final = [0] * n
for elem in t:
	if cur + 1 >= a[elem]:
		cur += 1
	else:
		cur = a[elem]
	final[elem] = cur
print(' '.join((str(x) for x in final)))


from operator import itemgetter
n = int(input())
a = list(map(int, input().split()))
b = sorted(enumerate(a), key=itemgetter(1))
for i in range(1, n):
	if a[b[i - 1][0]] >= a[b[i][0]]:
		a[b[i][0]] = a[b[i - 1][0]] + 1
print(' '.join(map(str, a)))


n = int(input())
lst = [*map(int, input().split())]
ind = sorted(range(n), key=lst.__getitem__)
elem = 0
for (i, x) in enumerate(ind):
	elem = max(elem + 1, lst[x])
	lst[x] = str(elem) + ' '
print(''.join(lst))


n = int(input())
arr = list(map(int, input().split()))
l = sorted(list(range(n)), key=lambda x: arr[x])
ans = [-1] * n
m = arr[l[0]]
for i in l:
	c = max(m, arr[i])
	ans[i] = c
	m = c + 1
print(*ans)


import sys

def main():
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split(' ')))
	l = sorted(list(range(n)), key=lambda i: a[i])
	cur = a[l[0]]
	s = set([cur])
	for i in range(1, n):
		if a[l[i]] == cur or a[l[i]] in s:
			a[l[i]] = cur + 1
		cur = a[l[i]]
		s.add(cur)
	sys.stdout.write('{}\n'.format(' '.join(list([str(i) for i in a]))))
main()


n = int(input())
a = list(map(int, input().split()))
t = 0
for x in sorted(list(range(n)), key=lambda t: a[t]):
	t = max(t + 1, a[x])
	a[x] = t
print(' '.join(map(str, a)))


from collections import defaultdict
from queue import *
n = int(input())
ratings = list(map(int, input().split(' ')))
value_ind_map = defaultdict(list)
res = [-1]
txt = []
for rating in sorted(ratings):
	if res[0] >= rating:
		res[0] = res[0] + 1
		value_ind_map[rating].append(res[0])
	else:
		res[0] = rating
		value_ind_map[rating].append(res[0])
for rating in ratings:
	txt.append(str(value_ind_map[rating].pop()))
print(' '.join(txt))


n = int(input())
x = list(map(int, input().split()))
a = [i for i in range(n)]
a.sort(key=lambda y: x[y])
c = 0
for i in range(n):
	if x[a[i]] <= c:
		x[a[i]] = c
		c += 1
	elif x[a[i]] > c:
		c = x[a[i]] + 1
x = list(map(str, x))
print(' '.join(x))


n = int(input())
a = list(map(int, input().split()))
b = [i for i in range(n)]
b.sort(key=lambda x: a[x])
res = 0
for i in range(n):
	if a[b[i]] <= res:
		a[b[i]] = res
		res += 1
	else:
		res = a[b[i]] + 1
print(*a, sep=' ')


n = int(input())
lis = list(map(int, input().split()))
li = sorted(list(range(len(lis))), key=lambda k: lis[k])
ans = [0] * n
prev = lis[li[0]]
ans[li[0]] = lis[li[0]]
for i in range(1, n):
	g = li[i]
	if prev >= lis[g]:
		prev += 1
		ans[g] = prev
	else:
		prev = lis[g]
		ans[g] = lis[g]
print(*ans)


n = int(input())
a = list(map(int, input().split()))
b = sorted(range(n), key=lambda i: a[i])
u = 0
for i in b:
	if a[i] <= u:
		u += 1
		a[i] = u
	else:
		u = a[i]
print(' '.join(map(str, a)))


dp = dict()
n = int(input())
a = list(map(int, input().split()))
g = sorted(list(range(n)), key=lambda x: a[x])
value = a[g[0]] - 1
for i in g:
	if a[i] <= value:
		a[i] = value + 1
		value += 1
	else:
		value = a[i]
print(' '.join(map(str, a)))


n = int(input())
b = sorted(((v, i) for (i, v) in enumerate(map(int, input().split()))))
ans = [0] * n
l = 0
for (y, x) in b:
	if y > l:
		l = y
	else:
		l += 1
	ans[x] = l
print(' '.join(map(str, ans)))


n = int(input())
values = list(map(int, input().split(' ')))
keys = sorted(range(n), key=lambda a: values[a])
last = 0
for a in keys:
	last = max(values[a], last)
	values[a] = last
	last += 1
print(*values)


n = int(input())
a = list(map(int, input().split(' ')))
id = sorted(range(n), key=lambda x: a[x])
for i in range(1, n):
	if a[id[i]] <= a[id[i - 1]]:
		a[id[i]] = a[id[i - 1]] + 1
print(' '.join(map(str, a)))


import operator
n = int(input())
a = list(((v, k) for (k, v) in enumerate(map(int, input().split()))))
a.sort(key=operator.itemgetter(0))
cur = 0
b = [0] * n
for i in range(n):
	x = a[i][0]
	if x > cur:
		cur = x + 1
		b[a[i][1]] = str(x)
	else:
		b[a[i][1]] = str(cur)
		cur += 1
print(' '.join(b))


n = int(input())
arr = list(map(int, input().split()))
ar = sorted(range(n), key=lambda x: arr[x])
mn = arr[ar[0]]
ans = [0] * n
ans[ar[0]] = arr[ar[0]]
for i in range(1, n):
	if arr[ar[i]] <= mn:
		mn = mn + 1
		ans[ar[i]] = mn
	else:
		mn = arr[ar[i]]
		ans[ar[i]] = mn
print(' '.join(map(str, ans)))


n = int(input())
x = list(map(int, input().split()))
ans = x.copy()
b = sorted(x.copy())
k = b[0] + 1
d = {b[0]: [1, b[0]]}
for i in range(1, n):
	if b[i - 1] == b[i]:
		d[b[i]].append(k)
		k += 1
	else:
		if b[i] < k:
			d[b[i]] = [1, k]
		else:
			d[b[i]] = [1, b[i]]
			k = b[i]
		k += 1
for j in range(n):
	ans[j] = d[x[j]][d[x[j]][0]]
	d[x[j]][0] += 1
print(*ans)


n = int(input())
arr = list(map(int, input().split(' ')))
arr1 = [(arr[i], i) for i in range(n)]
arr1 = sorted(arr1)
arr2 = [x[1] for x in arr1]
for i in range(1, n):
	if arr[arr2[i - 1]] >= arr[arr2[i]]:
		arr[arr2[i]] = arr[arr2[i - 1]] + 1
print(' '.join(map(str, arr)))


n = int(input())
a = list(map(int, input().split()))
sortedIndex = sorted(range(n), key=lambda k: a[k])
temp = 0
for i in range(n):
	if a[sortedIndex[i]] <= temp:
		a[sortedIndex[i]] = temp
		temp += 1
	elif a[sortedIndex[i]] > temp:
		temp = a[sortedIndex[i]] + 1
result = ' '.join((str(e) for e in a))
print(result)


i = int(input())
values = list(map(int, input().split(' ')))
result = [-1] * i
sortedValues = sorted(range(i), key=lambda x: values[x])
cnt = 0
for i in sortedValues:
	cnt = cnt + 1 if cnt + 1 >= values[i] else values[i]
	result[i] = cnt
print(' '.join([str(x) for x in result]))