[1] When there is a term on which no operation is performed

Since an operation always increases the value, we can assume that the term on which no operation is performed was the largest in \(A\).

Let \(a\) be the largest value in the initial state of \(A\). Then, we can assume that one of the following is done on each \(A_i\):

• Make it the smallest value greater than or equal to \(a\) that \(A_i\) can become.
• Make it the largest value less than or equal to \(a\) that \(A_i\) can become.

These smallest and largest values can be computed in \(O(\log a)\) time by considering each possible number of operations. Eventually, we want to solve the following problem:

You are given a sequence \((L_1, \ldots, L_N)\) of integers less than or equal to \(a\), and a sequence \((R_1, \ldots, R_N)\) of integers greater than or equal to \(a\). For each \(i\), you change \(A_i\) to \(L_i\) or \(R_i\). Minimize \(\max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\}\).

It can be solved as follows.

First, sort the values to make \(L_1\leq \cdots \leq L_N \leq a\). After fixing the minimum \(n\) for which we choose \(A_n = L_n\), it is optimal to choose \(A_i = R_i\) if \(i < n\) and \(A_i = L_i\) otherwise, in which case \(\max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\}\) can be easily computed.

[2] The full solution

First, solve the problem in [1] and let \(Y\) be the answer. Then, the answer to the whole problem turns out to be:

• \(0\) if \(Y < X\),
• \(Y\) if \(Y \geq X\).

Let us verify this.

First, assume that \(Y < X\). We want to prove the following:

If the difference between the largest and smallest of the sequence \((A_1, \ldots, A_N)\) is \(Y\) (\(0 < Y < X\)), it is possible to make the difference less than \(Y\) by performing one operation on each term appropriately.

After changing the minimum value \(A_i\) to \(2A_i + Y + 1\) and the maximum value \(A_j\) to \(2A_j\), the difference between them decreases to \(Y-1\). By also changing the values between the minimum and maximum appropriately, we can achieve our objective.

Next, assume that \(Y\geq X\). The process of performing some number of operations on every term in the sequence can be decomposed into the following two steps.

• Perform some number of operations under the restriction that there is a term on which no operation is performed.
• Then, repeat the following several times: perform one operation on every term.

When the first step is completed, the difference between the largest and smallest of the sequence will always be at least \(Y\). Then, it can be inductively proved using \(Y\geq X\) that the difference will remain at least \(Y\) after repeating the procedure in the second step any number of times. Therefore, the answer is \(Y\) in this case.

By summarizing the above, the whole problem can be solved in \(O(N(\log N + \log \max A_i))\) time.