Adjusting Drones

The process looks positional, but the first useful move is to stop staring at positions like they personally betrayed you.

For any value $x$ with frequency $c$ in the current array, one copy of $x$ stays at $x$, and the other $c-1$ copies become $x+1$. The original order only decides which identity survives. The resulting multiset is the same.

So we can sort the array and choose whatever tie-breaking rule makes the math clean.

Choose the right tie-breaker

Sort $a$ increasingly. When several elements currently have the same value, pretend the rightmost one is the copy that stays, and all earlier copies move.

This does not change the multiset after each operation. It only relabels identical drones. That is legal because the answer only depends on frequencies.

Now solve a stronger endpoint: what happens if we keep going until all values are distinct? This is the $k=1$ final state.

Let $b_i$ be the final value of sorted element $a_i$ under our rightmost-survives rule.

Process elements from right to left:

• when handling $a_i$, all elements to its right already claimed their final values;
• $a_i$ must eventually land on some unused value at least $a_i$;
• because it only increments by $1$, it lands on the smallest unused value $\ge a_i$.

So:

$$b_i = \min \{x \ge a_i : x \text{ is not already used by } b_{i+1},\ldots,b_n\}.$$

This can be computed with a DSU “next free position” structure, classic parking-lot stuff.

What is the value after exactly $m$ operations?

Under this tie-breaking rule, element $i$ just walks upward until it reaches $b_i$:

$$a_i, a_i+1, a_i+2, \ldots, b_i, b_i, b_i, \ldots$$

Therefore after $m$ operations its value is

$$c_i(m)=\min(a_i+m, b_i).$$

That is the key formula. No simulation. No drama.

Why is this true? If the element has not reached its final value yet, the value it wants to stay on is still occupied by some element to its right whose final value is there, so it gets pushed one step. Once it reaches $b_i$, nobody to its right will claim the same final value, so it stays forever.

Why binary search works

We need the first time when every value appears at most $k$ times.

The important monotonicity: the maximum frequency never increases after an operation.

Suppose a value $x+1$ has copies after an operation. They come from two places:

• copies of $x$ that moved from $x$ to $x+1$;
• possibly one copy of $x+1$ that stayed.

If $x$ had $c$ copies, at most $c-1$ moved. If $x+1$ had any copies, only one stayed. So the new count of $x+1$ is at most the previous maximum frequency. Thus once all frequencies are $\le k$, they stay that way.

So the predicate

$$\max_x \text{freq}_x(c_1(m),\ldots,c_n(m)) \le k$$

is monotonic in $m$.

Binary search the smallest valid $m$.

For a check, build all values $\min(a_i+m,b_i)$ and count frequencies. Values never exceed about $3n$, since $a_i \le 2n$ and an element moves at most $n-1$ steps. A plain frequency array is enough.

Algorithm

For each test case:

1. Sort $a$.
2. Compute $b$ from right to left using DSU next-free:
   • $b_i = \text{find}(a_i)$;
   • mark $b_i$ used by unioning it to $b_i+1$.
3. Binary search $m \in [0,n]$.
4. For each $m$, count values $\min(a_i+m,b_i)$ and test whether every count is at most $k$.

Complexity

Sorting costs $O(n\log n)$. The DSU work is almost linear. Each binary-search check is $O(n)$, and there are $O(\log n)$ checks.

Total:

$$O(n\log n)$$

per test case, with linear memory. Across all tests, this fits easily because $\sum n \le 2\cdot 10^5$.