Coffee Break
Contest: Hello 2025
Difficulty rating: 3500
Tags: data structures, greedy, math

There are very long classes in the T-Generation. In one day, you need to have time to analyze the training and thematic contests, give a lecture with new material, and, if possible, also hold a mini-seminar. Therefore, there is a break where students can go to drink coffee and chat with each other.

There are a total of $$$n+2$$$ coffee machines located in sequentially arranged rooms along a long corridor. The coffee machines are numbered from $$$0$$$ to $$$n+1$$$, and immediately after the break starts, there are $$$a_i$$$ students gathered around the $$$i$$$-th coffee machine.

The students are talking too loudly among themselves, and the teachers need to make a very important announcement. Therefore, they want to gather the maximum number of students around some single coffee machine. The teachers are too lazy to run around the corridors and gather the students, so they came up with a more sophisticated way to manipulate them:

- At any moment, the teachers can choose room $$$i$$$ ($$$1 \le i \le n$$$) and turn off the lights there;
- If there were $$$x$$$ students in that room, then after turning off the lights, $$$\lfloor \frac12 x \rfloor$$$ students will go to room $$$(i-1)$$$, and $$$\lfloor \frac12 x \rfloor$$$ other students will go to room $$$(i+1)$$$.
- If $$$x$$$ was odd, then one student remains in the same room.
- After that, the lights in room $$$i$$$ are turned back on.

The teachers have not yet decided where they will gather the students, so for each $$$i$$$ from $$$1$$$ to $$$n$$$, you should determine what is the maximum number of students that can be gathered around the $$$i$$$-th coffee machine.

The teachers can turn off the lights in any rooms at their discretion, in any order, possibly turning off the lights in the same room multiple times.

Note that the values of $$$a_0$$$ and $$$a_{n+1}$$$ do not affect the answer to the problem, so their values will not be given to you.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases.

In the first line of each test case, there is an integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

In the second line of each test case, there are integers $$$a_1, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the number of students around coffee machines numbered $$$1, 2, \ldots, n$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output $$$n$$$ integers $$$b_1, \ldots, b_n$$$, where $$$b_i$$$ is the maximum number of students that can be around coffee machines number $$$i$$$.

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

Note:
Let's analyze the first test case:

- To maximize the number of students at the $$$1$$$-st coffee machine, all that needs to be done is nothing.
- To maximize the number of students at the $$$2$$$-nd coffee machine, it is sufficient to turn off the lights in the $$$1$$$-st room once.

Example input:
3
2
8 0
5
2 2 2 2 2
5
0 0 9 0 0

Example output:
8 4 
4 5 4 5 4 
4 6 9 6 4

Editorial:
Let's call the elementary action $$$E_j$$$ the operation after which $$$a_j$$$ decreases by $$$2$$$, and the values $$$a_{j-1}$$$ and $$$a_{j+1}$$$ increase by $$$1$$$. Let $$$A$$$ be some set of actions that can be performed in some order; then this same set of actions can be performed greedily, each time performing any available elementary action. Our solution will be based on two facts:
• If we want to maximize $$$a_k$$$, then actions $$$E_1, \ldots E_{k-1}, E_{k+1}, \ldots E_n$$$ can be performed at any time, as long as it is possible.
• In this case, action $$$E_k$$$ cannot be performed at all.
The proof of the first fact is obvious. Suppose at some moment we can perform action $$$E_j$$$ ($$$j \neq k$$$); then if we do not apply it in the optimal algorithm, its application at that moment will not spoil anything. And if we do apply it, then let's apply this action right now instead of postponing it; this will also change nothing.
The proof of the second fact is slightly less obvious, so we will postpone it for later. For now, let's figure out how to emulate the application of elementary actions on the prefix $$$a_1, \ldots, a_{k-1}$$$ and on the suffix $$$a_{k+1}, \ldots, a_n$$$.
Without loss of generality, let's assume we are considering the prefix of the array $$$a$$$ of length $$$p$$$. Additionally, assume that $$$a_1, \ldots, a_{p-1} \le 1$$$, i.e., we cannot apply any of the actions $$$E_1, \ldots, E_{p-1}$$$. If $$$a_p \le 1$$$, then nothing can happen with this prefix for now. Otherwise, the only thing we can do is action $$$E_p$$$; after that, we may be able to apply action $$$E_{p-1}$$$, $$$E_{p-2}$$$, and so on. Let's see what happens if $$$a_p = 2$$$:
$$$$$$ [\ldots, 0, 1, 1, 1, 2] \to [\ldots, 0, 1, 1, 2, 0] \to \ldots \to [\ldots, 0, 2, 0, 1, 1] \to [\ldots, 1, 0, 1, 1, 1] $$$$$$
Thus, the position of the last zero in the prefix increases by one, and the value of $$$a_{p+1}$$$ also increases by one. We introduce a second elementary action $$$I_j$$$ — increasing $$$a_j$$$ by one if we previously decreased it by one. This action does not affect the answer, as it can be perceived as "reserving" $$$a_j$$$ for the future.
To understand what happens to the array $$$[a_1, \ldots, a_p]$$$ with an arbitrary value of $$$a_p$$$, we will assume that $$$a_p = 0$$$, but we will consider that we can apply action $$$I_p$$$ $$$x$$$ times, which increases $$$a_p$$$ by one. After each action $$$I_p$$$, we will emulate the greedy application of actions $$$E_1, \ldots, E_p$$$. This can be done as follows:
• In the stack $$$S$$$, we store the positions of zeros in the array $$$[a_1, \ldots, a_p]$$$ (the other values are equal to one).
• Let $$$l$$$ be the position of the last zero; then:
• If $$$l=p$$$, then this zero simply disappears from the stack.
• If $$$l<p$$$, then it is easy to emulate the next $$$p-l$$$ actions $$$I_p$$$: after each of them, the array looks like $$$[\ldots, 0, 1, 1, \ldots, 1, 2]$$$, and thus after the greedy application of actions $$$E_1, \ldots, E_p$$$, the value of $$$l$$$ increases by $$$1$$$.
• If the stack $$$S$$$ is empty, then after one action, $$$a_{p+1}$$$ increases by one, and the only element with index $$$1$$$ becomes zero. If we repeat actions after this point, the cases will break down identically with a period of $$$p+1$$$.
Thus, we have learned to understand what happens with each prefix of the array $$$a_1, \ldots, a_n$$$ if we greedily apply elementary actions $$$E_j$$$ ($$$1 \le j \le p$$$). In total, we can emulate these actions in $$$O(n)$$$ time.
Now let's return to the second point of the statement: if we want to maximize $$$a_k$$$, then we cannot perform actions $$$E_k$$$. Without loss of generality, let's assume that we first performed actions $$$E_j$$$ ($$$j \neq k$$$) greedily, and now we have $$$a_j \le 1$$$ ($$$j \neq k$$$). Suppose we performed action $$$E_k$$$ at least once; then after that, we will greedily perform elementary actions to the left and right, for which the stack scheme we considered above works. Notice that after this, the value of $$$a_k$$$ will increase by no more than $$$2$$$ (no more than $$$1$$$ after actions on the prefix and no more than $$$1$$$ after actions on the suffix). Thus, action $$$E_k$$$ after application did not lead to an increase in $$$a_k$$$, nor will it lead to an increase if we apply $$$E_k$$$ later, which means that it is useless—there is no need to perform it.
Thus, we have proven that by using elementary actions $$$E_1, \ldots, E_{k-1}, E_{k+1}, \ldots E_n$$$ based on the principle of "do while we can", we can easily maximize $$$a_k$$$. But in the original problem, we could not apply elementary actions. The operation in the problem, i.e., $$$a_{i-1} += \lfloor \frac12 a_i\ \rfloor$$$, $$$a_{i+1} += \lfloor \frac12 a_i\ \rfloor$$$, $$$a_i = a_i \bmod 2$$$, can be perceived as applying elementary actions $$$E_i$$$ consecutively while they are applicable. Fortunately, we just proved that actions can be performed in any order, which means that if we apply the operation from the problem for all indices $$$i \neq k$$$, we will eventually reach the same result, and the value of $$$a_k$$$ will reach its maximum.