[1] Existence of the answer

Let us begin by verifying that what the problem asks, “the maximum possible value of \(\min(A_1, A_2, \ldots, A_N)\) after your operations,” exists.

Since \(a\leq b\), the sum of the sequence \(A\) does not increase by the operation. Thus, in the final situation, we have \(\min(A_1, \ldots, A_N) \leq S/N\), where \(S\) is the initial sum of \(A\). This and the fact that \(A\) is always an integer sequence guarantee that the maximum possible value of \(\min(A_1, \ldots, A_N)\) exists.

---

[2] Using binary search

Consider finding the answer by binary search. For that, we are to solve the following decision problem for a constant \(C\):

• determine whether one can achieve \(\min(A_1, \ldots, A_N)\geq C\) by the operation.

We can rewrite the condition \(\min(A_1, \ldots, A_N)\geq C\) into separate conditions for respective terms, which is easier to handle, as follows:

• determine whether one can satisfy \(A_i\geq C\) for all \(i\).

---

[3] Solving the decision problem

For a sequence of operations to achieve our objective “\(A_i\geq C\) for all \(i\),” we can presume the following:

• One never applies both \(+a\) and \(-b\) to the same \(i\).

Indeed, assume that a sequence of operations achieving the objective contains both of the following:

• an operation applying \(+a\) to \(A_i\) and \(-b\) to \(A_j\);
• an operation applying \(-b\) to \(A_i\) and \(+a\) to \(A_k\).

We can reduce the number of operations in such a sequence while still satisfying the objective, by canceling these operations if \(j = k\), and replacing these operations with “an operation applying \(-b\) to \(A_j\) and \(+a\) to \(A_k\)” if \(j\neq k\). Therefore, one never applies both \(+a\) and \(-b\) to the same \(i\), when, for example, achieving the objective with the minimum number of operations.

Now, for each \(i\), we can compute the following \(x_i\) or \(y_i\):

• for \(i\) such that \(A_i < C\) initially: \(+a\) must be applied at least \(x_i\) times, but \(-b\) should not be applied;
• for \(i\) such that \(A_i \geq C\) initially: \(+a\) should not be applied, but \(-b\) may be applied at most \(y_i\) times.

There is a way to achieve these if and only if \(\sum x_i \leq \sum y_i\). This allows us to solve the decision problem.

---

[4] Summary

The decision problem can be solved in \(O(N)\) time.

As a lower bound for the binary search, the initial value of \(\min A_i\) can be used. As an upper bound, one can use the initial value of \(\sum A_i / N\) or \(\max A_i\) from the argument in [1]. Therefore, the whole problem can be solved in \(O\bigl(N\log (\max A_i - \min A_i)\bigr)\) time.