Array Reduction

Kill the positions

The array order is a scam here. Operations only care whether chosen values are equal or all different, so the whole problem depends only on the frequency of each value.

Let the positive frequencies be sorted:

$f_1 \ge f_2 \ge \dots \ge f_m$.

Think of each value as a vertical pile of copies. A same-value operation deletes from one pile. A distinct-value operation deletes at most one copy from each pile, like shaving off one horizontal layer.

Fix the number of distinct-value operations

Suppose we decide to use exactly $h$ distinct-value operations.

For one value with frequency $f_i$, those $h$ operations can delete at most $\min(f_i,h)$ copies of it, because each distinct-value operation can include that value only once.

So the total number deleted by the distinct-value operations is at most

$D(h)=\sum_i \min(f_i,h)$.

This upper bound is actually reachable: for operation layer $1,2,\dots,h$, take one copy from every value that still has a copy at that layer. All chosen values in one such operation are distinct, so it is legal.

After these $h$ distinct operations, value $i$ still has an excess of

$e_i(h)=\max(f_i-h,0)$

copies that distinct operations did not handle.

Now add same-value operations. One same-value operation can delete all remaining excess of one chosen value. Using two same-value operations on the same value is never useful for maximizing deletions, because you could merge them. So with $v$ same-value operations, you should pick the $v$ largest excesses.

Since the frequencies are sorted decreasing, the excesses $\max(f_i-h,0)$ are also sorted decreasing. Therefore, for fixed $h$ and $v$, the maximum removed count is

$D(h)+\sum_{i=1}^{v} \max(f_i-h,0)$.

That gives every possible strategy type: $h$ distinct-value operations and $v$ same-value operations, for total $h+v$ operations.

The efficient part

Naively trying every pair $(h,v)$ looks scary. It is not, if you only scan useful $v$.

For a fixed $h$, only frequencies with $f_i>h$ have positive excess. Let

$q_h = \#\{i : f_i>h\}$.

For this $h$, it is enough to try $v=0,1,\dots,q_h$. Larger $v$ would add zero useful deletion, so it cannot improve the minimum operation count.

The magic count is:

$\sum_h q_h = \sum_i f_i = n$.

Why? Each copy in a pile contributes to exactly one layer count. So across all $h$, the total scanning work is linear after sorting. No quadratic nonsense, no heroic suffering.

For each $h$:

1. Compute $D(h)$.
2. Start with deleted count $D(h)$ at operation count $h$.
3. Add excesses $f_1-h, f_2-h, \dots, f_{q_h}-h$ one by one.
4. After adding $v$ excesses, update best[h+v].

Here best[t] means the maximum number of elements removable using exactly this counted mix of useful operations. Then take prefix maximums so best[t] means maximum removable using at most $t$ operations.

Turning maximum deletion into exact final size

For target final size $x$, we need to delete

$k=n-x$

elements.

If best[t] >= k, then some plan deletes at least $k$ elements in at most $t$ operations. We can shrink the chosen sets inside those operations to delete exactly $k$: a subset of an all-equal set is still all equal, and a subset of an all-distinct set is still all distinct. Empty operations are just skipped.

So the answer for $x$ is the smallest $t$ such that best[t] >= n-x.

Complexity

Sorting frequencies costs $O(m\log m)$. The layer scanning costs $O(n)$. Over all tests, this is easily fine for $\sum n \le 3\cdot 10^5$.