F. Омкар и оползень
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Омкар стоит у подножия горы Селеста. Вершина находится в $$$n$$$ метрах от него, и он может видеть всю гору до вершины, поэтому для каждого $$$1 \leq j \leq n$$$ он знает, что высота горы в точке в $$$j$$$ метрах от него равна $$$h_j$$$. Известно, что для всех $$$j$$$ удовлетворяющих $$$1 \leq j \leq n - 1$$$, $$$h_j < h_{j + 1}$$$ (то есть высоты строго возрастают).

Внезапно происходит оползень! Пока происходит оползень, происходит следующее: каждую минуту, если $$$h_j + 2 \leq h_{j + 1}$$$, то один квадратный метр грязи будет скользить с позиции $$$j + 1$$$ в позицию $$$j$$$, так что $$$h_{j + 1}$$$ уменьшается на $$$1$$$, а $$$h_j$$$ увеличивается на $$$1$$$. Эти изменения происходят одновременно, так, например, если $$$h_j + 2 \leq h_{j + 1}$$$ и $$$h_{j + 1} + 2 \leq h_{j + 2}$$$ для какого-то $$$j$$$, то $$$h_j$$$ будет увеличено на $$$1$$$, $$$h_{j + 2}$$$ будет уменьшено на $$$1$$$, а $$$h_{j + 1}$$$ будет увеличено и уменьшено на $$$1$$$, что означает, что на самом деле $$$h_{j + 1}$$$ в течение этой минуты не изменится.

Оползень заканчивается, когда не будет такого $$$j$$$, что $$$h_j + 2 \leq h_{j + 1}$$$. Помогите Омкару выяснить, каковы будут значения $$$h_1, \dots, h_n$$$ после окончания оползня. Можно доказать, что при заданных ограничениях оползень всегда заканчивается через некоторое число минут.

Обратите внимание, что из-за большого количества входных данных, рекомендуется, чтобы ваш код использовал быстрый ввод.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$h_1, h_2, \dots, h_n$$$ удовлетворяющих $$$0 \leq h_1 < h_2 < \dots < h_n \leq 10^{12}$$$ — высоты.

Выходные данные

Выведите $$$n$$$ целых чисел, где $$$j$$$-е число  — это значение $$$h_j$$$ после остановки оползня.

Пример
Входные данные
4
2 6 7 8
Выходные данные
5 5 6 7
Примечание

Первоначально гора имеет высоты $$$2, 6, 7, 8$$$.

В первую минуту у нас есть $$$2 + 2 \leq 6$$$, таким образом $$$2$$$ увеличивается до $$$3$$$, а $$$6$$$ уменьшается до $$$5$$$, оставляя $$$3, 5, 7, 8$$$.

Во вторую минуту у нас есть $$$3 + 2 \leq 5$$$ и $$$5 + 2 \leq 7$$$, таким образом $$$3$$$ увеличивается до $$$4$$$, $$$5$$$ остается без изменений, а $$$7$$$ уменьшается до $$$6$$$, оставляя $$$4, 5, 6, 8$$$.

На третьей минуте у нас есть $$$6 + 2 \leq 8$$$, так что $$$6$$$ увеличивается до $$$7$$$, а $$$8$$$ уменьшается до $$$7$$$, оставляя $$$4, 5, 7, 7$$$.

На четвертой минуте у нас есть $$$5 + 2 \leq 7$$$, таким образом $$$5$$$ увеличивается до $$$6$$$, а $$$7$$$ уменьшается до $$$6$$$, оставляя $$$4, 6, 6, 7$$$.

На пятой минуте у нас есть $$$4 + 2 \leq 6$$$, поэтому $$$4$$$ увеличивается до $$$5$$$, а $$$6$$$ уменьшается до $$$5$$$, оставляя $$$5, 5, 6, 7$$$.

На шестой минуте ничего больше не может измениться, поэтому оползень останавливается, и наш ответ  — $$$5, 5, 6, 7$$$.