MEX Partition

The key is to not get baited by the word partition. It looks like you need to split the multiset cleverly, but the answer is actually forced.

Suppose some valid partition has score $x$. That means every multiset in the partition has MEX $x$.

For a multiset to have MEX $x$:

• it must contain every number $0,1,\dots,x-1$;
• it must contain no occurrence of $x$.

Now apply that to every part of the partition.

Since no part may contain $x$, the entire original multiset $A$ cannot contain $x$ either. There is nowhere to put it. If $x$ appeared in $A$, some part would have to receive it, and then that part's MEX would not be $x$. Instant contradiction.

Also, since each part contains all numbers smaller than $x$, the original multiset definitely contains all numbers $0,1,\dots,x-1$.

So any valid score $x$ must satisfy:

$$0,1,\dots,x-1 \text{ all appear in } A,$$

and

$$x \text{ does not appear in } A.$$

But that is literally the definition of $\operatorname{mex}(A)$.

So every valid partition has score exactly $\operatorname{mex}(A)$.

And we know this score is achievable, because we can use the dumbest possible partition: just one multiset, $A$ itself. Its MEX is $\operatorname{mex}(A)$, so the partition is valid.

Therefore the minimum score is simply:

$$\boxed{\operatorname{mex}(A)}$$

No splitting. No optimization. The problem put on a fake mustache and called itself partitioning.

Algorithm

For each test case:

1. Mark which values appear in $A$.
2. Starting from $0$, find the first value that does not appear.
3. Print it.

Since $n \le 100$ and values are at most $100$, checking up to about $101$ is enough.

Complexity

For each test case, the time complexity is $O(n + V)$ where $V$ is the small value range, around $101$.

Memory usage is $O(V)$.