Omkar and Landslide
Contest: Codeforces Global Round 10
Difficulty rating: 2400
Tags: binary search, constructive algorithms, data structures, greedy, math

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 format:
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 format:
Output $$$n$$$ integers, where the $$$j$$$-th integer is the value of $$$h_j$$$ after the landslide has stopped.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
4
2 6 7 8

Example output:
5 5 6 7

Editorial:
Fun fact: This problem was originally proposed as B.
TL;DR: We can show that in the resulting array, every pair of adjacent elements differs by exactly $$$1$$$ except that there may be at most one pair of adjacent equal elements. It is easy to see that there is only one such array satisfying that condition that also has the same length and sum as the given array, so we simply calculate that array based on the sum of the given array.
Proof: Clearly, the order in which we perform the slides (transfers of one square meter of dirt from $$$a_{j + 1}$$$ to $$$a_j$$$ for some $$$j$$$) does not matter. Consider then performing slides in the following manner: whenever we perform a slide from $$$a_j$$$ to $$$a_{j - 1}$$$, after that slide, if it is possible to perform a slide from $$$a_{j - 1}$$$ to $$$a_{j - 2}$$$, we will do so, and then from $$$a_{j - 2}$$$ to $$$a_{j - 3}$$$ and so on. We will call this action "performing a sequence of slides from $$$a_j$$$".
Assume that we have just performed a sequence of slides from $$$a_j$$$. We can see that if there was a pair of adjacent elements to the left of $$$a_j$$$ that were equal, i. e. some $$$k < j$$$ such that $$$a_{k - 1} = a_k$$$, then, assuming that $$$a_{k -1}, a_k$$$ is the rightmost such pair, then the sequence of slides that we started will end with $$$a_k$$$ being increased. In this case, $$$a_{k - 1}$$$ and $$$a_k$$$ are no longer equal, but $$$a_k, a_{k + 1}$$$ may now be equal, so the amount of pairs of adjacent equal elements to the left of $$$a_j$$$ has either decreased or stayed the same.
On the other hand, if there was no such pair, then the sequence of slides would end with $$$a_1$$$ being increased, meaning it might now be true that $$$a_1$$$ and $$$a_2$$$ are equal, so that the amount of pairs of adjacent equal elements to the left of $$$a_j$$$ is either still $$$0$$$ or now $$$1$$$.
Combining these two facts, we see that if there were either $$$0$$$ or $$$1$$$ pairs of adjacent equal elements to the left of $$$a_j$$$ to start with, then there will only be either $$$0$$$ or $$$1$$$ pairs of adjacent equal elements to the left of $$$a_j$$$ after performing a sequence of slides from $$$a_j$$$.
Noting that as our array is initially strictly increasing, there are initially no pairs of adjacent equal elements, we can simply first perform as many sequences of slides from $$$a_2$$$ as possible, then perform as many sequences of slides from $$$a_3$$$ as possible, and so on, until we perform as many sequences of slides from $$$a_n$$$ as possible. When we are performing sequences of slides from $$$a_j$$$, there can clearly only be either $$$0$$$ or $$$1$$$ pairs of adjacent equal elements to the left of $$$a_j$$$, and there can't be any such pairs to the right of $$$a_j$$$ as that part of the array hasn't been touched yet and is therefore still strictly increasing. Therefore, we can conclude that once all possible slides have been performed, the entire array will contain at most $$$1$$$ pair of adjacent equal elements.
Since it cannot be possible to perform any more slides once all possible slides have been performed, all pairs of adjacent elements that are not equal must differ by at most $$$1$$$. It is easy to see that there is only one array satisfying these conditions that has the same length $$$n$$$ and sum $$$S = \sum_{j = 1}^n a_j$$$. You can construct this array by starting with the array $$$0, 1, 2, \dots, n - 1$$$, then adding $$$1$$$ to each element from left to right, looping back to the beginning when you reach the end, until the sum of the array is $$$S$$$. From this construction we can derive the following formula for the array:
$$$a_j = j - 1 + \lfloor \frac {S - \frac {n(n - 1)} 2} n \rfloor + \{j \leq (S - \frac {n(n - 1)} 2) \% n\}$$$
where $$$\{C\}$$$ is $$$1$$$ if the condition $$$C$$$ is satisfied, and $$$0$$$ otherwise.