Omkar is standing at the foot of Celeste mountain. The summit is $n$ meters away from him, and he can see all of the mountains up to the summit, so for all $1 \leq j \leq n$ he knows that the height of the mountain at the point $j$ meters away from himself is $h_j$ meters. It turns out that for all $j$ satisfying $1 \leq j \leq n - 1$, $h_j < h_{j + 1}$ (meaning that heights are strictly increasing).

Suddenly, a landslide occurs! While the landslide is occurring, the following occurs: every minute, if $h_j + 2 \leq h_{j + 1}$, then one square meter of dirt will slide from position $j + 1$ to position $j$, so that $h_{j + 1}$ is decreased by $1$ and $h_j$ is increased by $1$. These changes occur simultaneously, so for example, if $h_j + 2 \leq h_{j + 1}$ and $h_{j + 1} + 2 \leq h_{j + 2}$ for some $j$, then $h_j$ will be increased by $1$, $h_{j + 2}$ will be decreased by $1$, and $h_{j + 1}$ will be both increased and decreased by $1$, meaning that in effect $h_{j + 1}$ is unchanged during that minute.

The landslide ends when there is no $j$ such that $h_j + 2 \leq h_{j + 1}$. Help Omkar figure out what the values of $h_1, \dots, h_n$ will be after the landslide ends. It can be proven that under the given constraints, the landslide will always end in finitely many minutes.

Note that because of the large amount of input, it is recommended that your code uses fast IO.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^6$). 

The second line contains $n$ integers $h_1, h_2, \dots, h_n$ satisfying $0 \leq h_1 < h_2 < \dots < h_n \leq 10^{12}$ — the heights.


-----Output-----

Output $n$ integers, where the $j$-th integer is the value of $h_j$ after the landslide has stopped.


-----Example-----
Input
4
2 6 7 8

Output
5 5 6 7



-----Note-----

Initially, the mountain has heights $2, 6, 7, 8$.

In the first minute, we have $2 + 2 \leq 6$, so $2$ increases to $3$ and $6$ decreases to $5$, leaving $3, 5, 7, 8$.

In the second minute, we have $3 + 2 \leq 5$ and $5 + 2 \leq 7$, so $3$ increases to $4$, $5$ is unchanged, and $7$ decreases to $6$, leaving $4, 5, 6, 8$.

In the third minute, we have $6 + 2 \leq 8$, so $6$ increases to $7$ and $8$ decreases to $7$, leaving $4, 5, 7, 7$.

In the fourth minute, we have $5 + 2 \leq 7$, so $5$ increases to $6$ and $7$ decreases to $6$, leaving $4, 6, 6, 7$.

In the fifth minute, we have $4 + 2 \leq 6$, so $4$ increases to $5$ and $6$ decreases to $5$, leaving $5, 5, 6, 7$.

In the sixth minute, nothing else can change so the landslide stops and our answer is $5, 5, 6, 7$.

Source: codeforces | Difficulty: VERY_HARD
Tags: Constructive algorithms

Sorting

Greedy algorithms

Mathematics

Data structures


Solutions:
from collections import deque
from collections import OrderedDict
import math
import sys
import os
import threading
import bisect
import operator
import heapq
from atexit import register
from io import BytesIO
import io
from sys import stdin, stdout
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		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 = os.read(self._fd, max(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 = os.read(self._fd, max(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:
			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')
n = int(input())
lis = list(map(int, input().split()))
sumAr = 0
for i in range(n):
	sumAr += lis[i]
k = (sumAr - n * (n - 1) // 2) // n
dif = sumAr - (k * n + n * (n - 1) // 2)
answer = []
for i in range(n):
	if i < dif:
		print(k + i + 1)
	else:
		print(k + i)
sys.exit(0)

class Person:

	def __init__(self, name, age):
		self.name = name
		self.age = age
p1 = Person('heelo', 27)
print(help(Person))
age = 26
name = 'Swaroop'
print('Возрас {} -- {} лет'.format(name, age))
print(help(object))


from collections import *
from sys import stdin, stdout
input = stdin.buffer.readline
print = stdout.write

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
n = ri()
h = rl()
sum = 0
for i in range(n):
	sum += h[i]
sum -= int(n * (n - 1) / 2)
x = sum // n + 1
a = sum % n
for i in range(a):
	print(str(x + i) + ' ')
for i in range(a, n):
	print(str(x - 1 + i) + ' ')
print('\n')


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import sys
n = int(input())
SUM = sum(map(int, input().split()))
OK = SUM // n - n // 2 - 10
NG = SUM // n - n // 2 + 10

def tousa(s, n):
	return (s + (s + n - 1)) * n // 2
while NG - OK > 1:
	mid = (OK + NG) // 2
	if tousa(mid, n) > SUM:
		NG = mid
	else:
		OK = mid
rest = SUM - tousa(OK, n)
for i in range(n):
	if i < rest:
		sys.stdout.write(str(OK + i + 1) + ' ')
	else:
		sys.stdout.write(str(OK + i) + ' ')


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline
	N = int(input())
	A = list(map(int, input().split()))
	S = sum(A)
	k = (S - (N - 1) * (N - 2) // 2) % N
	x = (S - (N - 1) * (N - 2) // 2 - k) // N
	for i in range(N - 1):
		sys.stdout.write(str(x + i) + ' ')
		if i == k:
			sys.stdout.write(str(x + i) + ' ')
	if k == N - 1:
		sys.stdout.write(str(x + k) + ' ')
main()


from sys import stdin, stdout
input = stdin.buffer.readline
print = stdout.write

def f(a, b):
	return (a + b) * n // 2
n = int(input())
(*h,) = map(int, input().split())
s = sum(h)
(l, r) = (0, 10 ** 12)
while l < r:
	m = l + r >> 1
	if f(m, m + n - 1) < s:
		l = m + 1
	else:
		r = m
l -= 1
y = f(l, l + n - 1)
for i in range(n):
	print(f'{l + i + (i < s - y)} ')


n = int(input().strip())
a = [int(ai) for ai in input().strip().split()]
l = 1
r = max(a)
asum = sum(a)
ans = 0
while l <= r:
	mid = l + r >> 1
	if 2 * n * mid >= 2 * asum - n * n - n:
		r = mid - 1
		ans = mid
	else:
		l = mid + 1
asum = asum - (ans + ans + n - 1) * n // 2
for i in range(0, n):
	a[i] = ans + int(asum > 0)
	ans = ans + 1
	asum = asum - 1
print(' '.join((str(ai) for ai in a)))


N = int(input())
s = sum([int(a) for a in input().split()])
a = N * (N - 1) // 2
b = (s - a) % N
c = (s - a) // N
print(' '.join(map(str, [i + c + 1 if i < b else i + c for i in range(N)])))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		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 = os.read(self._fd, max(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 = os.read(self._fd, max(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:
			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')
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
s1 = (s - n * (n - 1) // 2) // n
s2 = (s - n * (n - 1) // 2) % n
for i in range(n):
	a[i] = i + s1 + (i + 1 <= s2)
print(*a)


n = int(input())
tot = sum(map(int, input().split()))
extra = n * (n - 1) // 2
smol = (tot - extra) // n
out = [smol + i for i in range(n)]
for i in range(tot - sum(out)):
	out[i] += 1
print(' '.join(map(str, out)))


import os
import sys
from io import BytesIO, IOBase

def main():
	n = getint()
	a = getints()
	s = sum(a) - n * (n - 1) // 2
	(start, offset) = (s // n, s % n)
	for i in range(n):
		a[i] = start + i + int(i < offset)
	print(*a)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		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 = os.read(self._fd, max(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 = os.read(self._fd, max(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:
			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))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def getint():
	return int(input())

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

def getint1():
	return list(map(lambda x: int(x) - 1, input().split()))
main()


import sys
input = sys.stdin.readline
n = int(input())
l = list(map(int, input().split()))
x = sum(l)
y = x // n - n // 2 - 2
while y * n + n * (n - 1) // 2 <= x:
	y += 1
y -= 1
cut = x - (y * n + n * (n - 1) // 2)
ans = [i + y + 1 for i in range(cut)]
ans += [i + y + cut for i in range(n - cut)]
print(' '.join(map(str, ans)))


n = int(input())
h = list(map(int, input().split()))
s = sum(h)
a = n * (n + 1) // 2
result = (s - a) // n
rest = (s - a) % n
print(*[i + result + 1 if i <= rest else i + result for i in range(1, n + 1)])


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
s -= (n * n - n) // 2
k = s // n
r = s % n
ans = []
for i in range(n):
	curAns = k + i
	if r > i:
		curAns += 1
	ans.append(str(curAns))
print(' '.join(ans))


import sys, math, cmath, time
start_time = time.time()

def solve():
	n = inp()
	a = inlt()
	q = (sum(a) - n * (n - 1) // 2) // n
	qq = 0
	ww = sum(a)
	for i in range(n):
		qq = qq + q + i
	for i in range(n):
		if i < ww - qq:
			qw = q + i + 1
		else:
			qw = q + i
		sys.stdout.write(str(qw) + ' ')

def main():
	global tt
	if not ONLINE_JUDGE:
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	t = 1
	for tt in range(t):
		solve()
	if not ONLINE_JUDGE:
		print('Time Elapsed :', time.time() - start_time, 'seconds')
		sys.stdout.close()

def inp():
	return int(input())

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

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

def invr():
	return map(int, input().split())

def counter(a):
	q = [0] * max(a)
	for i in range(len(a)):
		q[a[i] - 1] = q[a[i] - 1] + 1
	return q

def counter_elements(a):
	q = dict()
	for i in range(len(a)):
		if a[i] not in q:
			q[a[i]] = 0
		q[a[i]] = q[a[i]] + 1
	return q

def string_counter(a):
	q = [0] * 26
	for i in range(len(a)):
		q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
	return q

def factors(n):
	q = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			q.append(i)
			q.append(n // i)
	return list(sorted(list(set(q))))

def prime_factors(n):
	q = []
	while n % 2 == 0:
		q.append(2)
		n = n // 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			q.append(i)
			n = n // i
	if n > 2:
		q.append(n)
	return list(sorted(q))

def transpose(a):
	(n, m) = (len(a), len(a[0]))
	b = [[0] * n for i in range(m)]
	for i in range(m):
		for j in range(n):
			b[i][j] = a[j][i]
	return b

def factorial(n, m=1000000007):
	q = 1
	for i in range(n):
		q = q * (i + 1) % m
	return q
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	import io, os
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()


n = int(input())
num = list(map(int, input().split()))
s1 = n * (n - 1) // 2
su = sum(num)
s2 = su - s1
base = s2 // n
additional = s2 % n
out = []
for i in range(n):
	val = base + i
	if additional > 0:
		additional -= 1
		val += 1
	out.append(str(val))
print(' '.join(out))


import sys
n = int(input())
a = [int(v) for v in sys.stdin.readline().split()]
s = sum(a) - n * (n + 1) // 2
p = s // n
q = s % n
for j in range(n):
	a[j] = j + 1 + p + (q > 0)
	q = q - 1
print(' '.join(map(str, a)))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		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 = os.read(self._fd, max(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 = os.read(self._fd, max(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:
			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')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
n = N()
d = RLL()
s = sum(d) - (n ** 2 - n >> 1)
c = n
kk = 0
for i in range(n - 1, 0, -1):
	if d[i] - i > s // c:
		kk = i
		break
	c -= 1
	s -= d[i] - i
for i in range(kk, 0, -1):
	tmp = s // c
	c -= 1
	s -= tmp
	d[i] = tmp + i
d[0] = s
print_list(d)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		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 = os.read(self._fd, max(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 = os.read(self._fd, max(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:
			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')

def bsearch(mn, mx, func):
	idx = (mx + mn) // 2
	while mx - mn > 1:
		if func(idx):
			(idx, mx) = ((idx + mn) // 2, idx)
			continue
		(idx, mn) = ((idx + mx) // 2, idx)
	return idx
(N,) = map(int, input().split())
X = list(map(int, input().split()))
sX = sum(X)
d = X[0]
if sX >= N * (N - 1) // 2:
	tmp = sX - N * (N - 1) // 2
	d = max(tmp // N, d)
m = sX - d * N
for i in range(N):
	X[i] = d
i = bsearch(0, N, lambda i: i * (i + 1) // 2 >= m)
i += 1
for j in range(i - 1):
	X[N - 1 - j] += i - j - 1
k = m - i * (i - 1) // 2
for j in range(k):
	X[N - i + j] += 1
print(' '.join(map(str, X)))