Candies

Let $\operatorname{pos}_x$ be the initial position of child $x$.

Suppose a child is currently at position $p$ and has $c$ candies. In one operation, the leftmost chosen child moves two positions to the right and receives one candy, while each of the other two children moves one position to the left and receives one candy. Therefore, for every child, $p+c\equiv \operatorname{pos}_x\pmod3$ is invariant.

The three children chosen in an operation have the same number of candies. Hence the residues modulo $3$ of their initial positions are all different. Therefore, two children whose initial positions have the same residue modulo $3$ can never change their relative order.

In particular, the children initially at positions $i$ and $i+3$ must appear in the same relative order in the final arrangement. Since the final arrangement is increasing by child number, $P_i<P_{i+3}$ must hold for every . If this condition fails, the answer is .

Assume from now on that this condition holds.

In the final arrangement, child $i$ must be at position $i$. If this child initially stood at position $\operatorname{pos}_i$ and ends with $H_i$ candies, the invariant gives .

Now ignore the identities of the children and look only at the number of candies at each position. If three consecutive positions all contain children with $h$ candies, one operation changes their values from $h,h,h$ to $h+1,h+1,h+1$. Thus, an operation can be viewed as placing a horizontal block of length on a bar chart.

Suppose the final candy counts are $H_1,H_2,\ldots,H_N$. For any positive integer , consider the positions satisfying . Every maximal consecutive segment of such positions must have length divisible by , because one layer can only be formed by blocks of length .

This condition is also sufficient. Process the layers from bottom to top. For each layer $k$, split every maximal segment with height at least $k$ into blocks of three consecutive positions and perform one operation on each block. Immediately before constructing layer $k$, the three selected positions all have exactly $k-1$ candies, so every operation is valid.

Therefore, it remains to choose $H_1,H_2,\ldots,H_N$ such that for every , while every layer consists of consecutive segments whose lengths are divisible by . Since every operation increases the total number of candies by exactly , the number of operations is .

Determine the values $H_i$ from left to right. For every height $k$, let $S_k$ be the length modulo $3$ of the last currently open consecutive segment on layer .

If $S_k\ne0$, the current segment on layer $k$ has not been completed yet. Therefore, the next position must also have height at least $k$. Let $$ be the largest such that . If no such exists, let .

The next value $H_i$ must be at least $M$, and it must satisfy $H_i\equiv \operatorname{pos}_i-i\pmod3$. Choose the smallest integer satisfying both conditions.

This greedy choice is optimal. Choosing a value below $M$ is impossible because it would terminate an unfinished segment. Any larger value with the same residue differs by at least $3$. Those additional three layers do not help complete any existing unfinished layer; they only start new unfinished segments. Hence there is never a benefit in choosing a larger value.

After choosing $H_i$, the last segment on every layer from $1$ through $H_i$ is extended by one position. Therefore, add $1$ modulo to .

After all positions have been processed, if some $S_k\ne0$ remains, then the last segment on that layer has length not divisible by $3$, so the target is impossible. Otherwise, the heights chosen by the greedy algorithm are optimal.

We need two operations on the sequence $S$: add $1$ modulo $3$ to a prefix $S_1,\ldots,S_H$, and find the largest such that . Both can be supported with a lazy segment tree.

For each node, store a $3$-bit mask describing which values among $0,1,2$ occur in that interval. Bit $j$ is set if some $S_k=j$ exists in the interval. Adding modulo maps the states to , so the mask can be updated by a cyclic rotation of its three bits.

To find the largest $k$ with $S_k\ne0$, descend from the root while checking the right child first and choosing a child whose mask contains state $1$ or $$.

Each new $H_i$ is at most $M+2$, so it is sufficient to maintain heights only up to $2N$.

The time complexity is $O(N\log N)$, and the memory complexity is $O(N)$.

Solution written by GPT5.6