If we can do all operations and all $$$a_i$$$ remain non-negative, then the sum of $$$a_i$$$ is at least the sum of $$$b_j$$$ ($$$\sum a \ge \sum b$$$). Since we consider $$$k$$$ operations, each $$$a_i$$$ cannot contribute more than $$$k$$$ times, we can replace it by $$$\min(a_i, k)$$$. And then we check that the sum is still at least the sum of $$$b$$$. The assumption that $$$b$$$ is non-increasing is here because we want to verify the condition only for the maximal set of $$$k$$$ operations. If we can do $$$k$$$ maximal operations then we can do every other set of $$$k$$$ operations.

To show that, I want to prove that swapping two adjacent operations $$$k_1$$$ and $$$k_2$$$ is possible. if $$$k_1 = k_2$$$, it's trivial. Then, without loss of generality, $$$k_1 \gt k_2$$$.

Assume the array $$$a$$$ is sorted. The operations will decrease such positions that the array remains sorted. In order to do that, we pick positions from greater values left to right. For example, the red $$$8$$$ positions in this array would be picked.

$$$[1, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 6, 7, 8, 8]$$$

$$$[1, 2, 3, 3, \color{red}{4}, \color{red}{4}, 4, 4, 4, 4, \color{red}{5}, \color{red}{5}, \color{red}{6}, \color{red}{7}, \color{red}{8}, \color{red}{8}]$$$

Notice that an operation decreases some suffix and some prefix of the next value. Also, this is the only way to remain the array sorted.

We show that the multiset of indices selected by the $$$k_1$$$ and $$$k_2$$$ operations is the same regardless of whether $$$k_1$$$ is applied before $$$k_2$$$ or $$$k_2$$$ before $$$k_1$$$. Since there is no ambiguity in the choice of positions, we can actually only look at the number of positions with a certain value that were decreased zero, once or twice.

Denote $$$c_x$$$ as the frequency of $$$x$$$ in the array $$$a$$$.

Let's start with a simple case where the first operations only decreases the maximum value $$$x$$$. If $$$k_1 + k_2 \le c_x$$$, then the first $$$k_1 + k_2$$$ positions where $$$x$$$ is will be decreased. if $$$k_1 + k_2 \ge c_x$$$, then:

• If we apply $$$k_1$$$ first and then $$$k_2$$$, the first operation decreases $$$k_1$$$ entries equal to $$$x$$$. The second operation decreases the remaining $$$c_x - k_1$$$ entries equal to $$$x$$$, and then decreases entries equal to $$$x-1$$$ (some of which may have been equal to $$$x$$$ before applying $$$k_1$$$). Crucially, after applying $$$k_1$$$ there are at least $$$k_1$$$ occurrences of $$$x-1$$$, so the $$$k_2$$$ operation only affects values equal to $$$x$$$ or $$$x-1$$$. Consequently, all entries equal to $$$x$$$ become $$$x-1$$$, and exactly $$$k_2 - (c_x - k_1) = k_1 + k_2 - c_x$$$ entries equal to $$$x-1$$$ are further decreased.

• If we apply $$$k_2$$$ first and then $$$k_1$$$, the first operation decreases $$$k_2$$$ entries equal to $$$x$$$. The second operation decreases the remaining $$$c_x - k_2$$$ entries equal to $$$x$$$, and then decreases $$$k_1 + k_2 - c_x \le k_2$$$ entries equal to $$$x-1$$$. The inequality ensures that no other values are affected. Again, all entries equal to $$$x$$$ become $$$x-1$$$, and exactly $$$k_1 + k_2 - c_x$$$ entries equal to $$$x-1$$$ are decreased.

Now consider the more general case where $$$x$$$ is the maximum number such that $$$c_x + c_{x+1} + \ldots \gt k_1$$$. If no such $$$x$$$ exists, then $$$k_1 = n$$$, which means that all numbers are decreased by $$$1$$$ and the order of indices which we choose for $$$k_2$$$ won't change, so the swap of operations doesn't affect the resulting array.

Otherwise the first operation $$$k_1$$$ would look like this:

Red stripes show the positions that are decreased. We can split the array $$$a$$$ in four parts: $$$ \lt x$$$, $$$x$$$, $$$x+1$$$, $$$ \gt x+1$$$ (some of them, but not $$$x$$$, might be empty). Denote the number of decreased $$$x$$$-s as $$$L$$$ and the number of elements in the fourth part as $$$R$$$. As was mentioned before, the operation decreases some suffix and some prefix of entries of the number before it.

Assume $$$k_2 \le R$$$. Let's look at the sets of positions which $$$k_2$$$ would decrease if it's the first and if it's the second operation. They are the same, since the order, in which we pick indices, of the $$$R$$$ positions doesn't change after applying $$$k_1$$$ first, as it decreases all values in that suffix and all entries of the value before. On the other hand the sets of positions which $$$k_1$$$ would decrease are also the same. In both cases the number of elements that are greater than $$$x$$$ is the same and less than $$$k_1$$$, so all of them will be decreased. The remaining prefix is unaffected by $$$k_2$$$, so the order of positions chosen in the prefix is also the same.

Now let's look at another case, where $$$k_2 \gt R$$$. I claim that the last $$$R$$$ elements will be decreased twice, hence can be ignored.

• first $$$k_1$$$ then $$$k_2$$$ — $$$k_1$$$ doesn't change the order of the first $$$R$$$ indices which are then chosen by $$$k_2$$$.

• first $$$k_2$$$ then $$$k_1$$$ — $$$k_2$$$ doesn't change the number of elements that are greater than $$$x$$$, so $$$k_1$$$ will decrease all of them, including all positions in $$$R$$$.

Now the problem reduces to $$$k_1$$$ decreasing only two distinct values. Once again, there are two cases.

1. $$$k_2 \le c_{x+1}$$$. Then let's look at the amount of entries of each value that will be decreased.

• first $$$k_1$$$ then $$$k_2$$$ — $$$k_1$$$ will decrease $$$c_{x+1}$$$ entries of $$$x+1$$$ and $$$k_1 - c_{x+1}$$$ entries of $$$x$$$. $$$k_2$$$ will then decrease $$$k_2$$$ entries of $$$x$$$, since $$$c_{x+1} \ge k_2$$$.

• first $$$k_2$$$ then $$$k_1$$$ — $$$k_2$$$ will decrease $$$k_2$$$ entries of $$$x+1$$$. $$$k_1$$$ will decrease $$$c_{x+1} - k_2$$$ entries of $$$x+1$$$ and $$$k_1 + k_2 - c_{x+1} \lt c_x + k_2$$$ entries of $$$x$$$. The inequality shows that $$$k_1$$$ will only decrease entries of $$$x$$$ and $$$x+1$$$.

1. $$$k_2 \gt c_{x+1}$$$. This case is tedious as there are subcases with $$$x - 1$$$, but the logic is the same, so I leave it as an exercise to the reader :)

Therefore, in all cases both orders of operations result in the same array, so we can swap adjacent operations without any effect. And if we can swap adjacent operations, we can get any permutation of operations we want.

Consider a function $$$f(k) = \sum \limits_{i=1}^n \min(k, a_i) - kt$$$. We want to find its minimum to check if it's less than $$$0$$$.

$$$f(k + 1) - f(k) = \sum \limits_{i=1}^n \min(k + 1, a_i) - \min(k, a_i) - t$$$. The sum of the differences of the minima is the number of $$$a_i \gt k$$$, which decreases with $$$k$$$, so $$$f$$$ is a concave function. That means that the minimum value is either $$$f(0)$$$ or $$$f(m)$$$. Since $$$f(0) = 0$$$ we only need to check $$$f(m)$$$.

For each window of size $$$k$$$ we choose $$$k$$$ different colors and decrease their frequency by $$$1$$$. That's exactly the process of the Theorem. The last window will have size $$$n \mod k$$$, there we put all the remaining colors. So we have operations $$$b_1 = b_2 = \ldots = b_{\lfloor \frac{n}{k} \rfloor} = k, b_{\lfloor \frac{n}{k} \rfloor} + 1 = n \mod k$$$. From the previous fact there are only two conditions we need to check, for the first $$$\lfloor \frac{n}{k} \rfloor$$$ operations and for all of them.

1. $$$\sum \limits_{i=1}^m \min(\lfloor \frac{n}{k} \rfloor, a_i) \ge n - n \mod k$$$

2. $$$\sum \limits_{i=1}^m \min(\lfloor \frac{n}{k} \rfloor + 1, a_i) \ge n$$$

The first condition means that there are at most $$$n \mod k$$$ values in $$$a$$$ that are greater than $$$\lfloor \frac{n}{k} \rfloor$$$.

The second condition together with the fact that $$$\sum a = n$$$ means that $$$\max(a) \le \lfloor \frac{n}{k} \rfloor + 1$$$.

Lastly, how do we select the colors for each cell? For the first window we just pick $$$n \mod k$$$ most frequent colors and then for each window of size $$$k$$$ we first pick colors and then from left to right select any color that can be put. It works because of pigeonhole principle (there are more allowed colors we can put than the number of banned colors).

We have

$$$\sum \limits_{i=1}^m min(k, b_i) \ge \sum \limits_{i=1}^k a_i$$$.

Since all $$$b_i = t$$$, this becomes

$$$m \cdot min(k, t) \ge \sum \limits_{i=1}^k a_i$$$.

For $$$k \le t$$$, this gives $$$km \ge \sum \limits_{i=1}^k a_i$$$. In particular, for $$$k = 1$$$ we obtain $$$m \ge a_1$$$, and since $$$a_1 \ge a_i$$$, this inequality also implies $$$km \ge ka_1 \ge \sum \limits_{i=1}^k a_i$$$ for every $$$k \le t$$$.

For $$$k \gt t$$$ the left-hand side is always $$$tm$$$, while the right-hand side increases till $$$\sum a$$$. Hence it suffices to check only $$$k = 1$$$ and $$$k = n$$$ to find minimal $$$m$$$.

1. $$$k = 1$$$. $$$m \ge a_1$$$

2. $$$k = n$$$. $$$tm \ge \sum a \Rightarrow m \ge \lceil \frac{\sum a}{t} \rceil$$$

Therefore $$$m = \max(a_1, \lceil \frac{\sum a}{t} \rceil)$$$.

1. The greedy algorithm to always decrease maximums produces the lexicographically largest possible sorted array among all arrays which are achievable with the operations.