Jellyfish and Mex
Contest: Codeforces Round 901 (Div. 2)
Difficulty rating: 1600
Tags: dp

You are given an array of $$$n$$$ nonnegative integers $$$a_1, a_2, \dots, a_n$$$.

Let $$$m$$$ be a variable that is initialized to $$$0$$$, Jellyfish will perform the following operation $$$n$$$ times:

- select an index $$$i$$$ ($$$1 \leq i \leq |a|$$$) and delete $$$a_i$$$ from $$$a$$$.
- add $$$\operatorname{MEX}(a)^{\dagger}$$$ to $$$m$$$.

Now Jellyfish wants to know the minimum possible final value of $$$m$$$ if he performs all the operations optimally.

$$$^{\dagger}$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

- The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
- The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
- The MEX of $$$[0,3,1,2]$$$ is $$$4$$$ because $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ belong to the array, but $$$4$$$ does not.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 5000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 5000$$$) — the size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the integers in the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output format:
For each test case, output a single integer — the minimum value of $$$m$$$ if the operations are performed optimally.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we delete elements from $$$a$$$ in the following order: $$$[5,2,\color{red}{1},0,3,0,4,0] \to [5,2,0,3,\color{red}{0},4,0] \to [5,2,\color{red}{0},3,4,0] \to [5,2,3,4,\color{red}{0}] \to [5,2,\color{red}{3},4] \to [\color{red}{5},2,4] \to [\color{red}{2},4] \to [\color{red}{4}] \to [~]$$$. The value of $$$m$$$ will be $$$1+1+1+0+0+0+0+0=3$$$.

Example input:
4
8
5 2 1 0 3 0 4 0
2
1 2
5
1 0 2 114514 0
8
0 1 2 0 1 2 0 3

Example output:
3
0
2
7

Editorial:
We only care about the operation before $$$\text{mex}(S)$$$reaches $$$0$$$, because after that, $$$m$$$ will never change.
Before $$$\text{mex}(S)$$$ reaches $$$0$$$, we will choose a positive integer $$$x$$$ at a time that satisfies $$$x < \text{mex}(S)$$$, and delete all $$$x$$$ from $$$S$$$, the $$$\text{mex}(S)$$$ will become $$$x$$$.
Because if $$$x > \text{mex}(S)$$$, We can place this operation after the $$$\text{mex}(S)$$$ becomes $$$0$$$, if we don't delete all of $$$x$$$, we can also put this operation later.
So before $$$\text{mex}(S)$$$ reaches $$$0$$$, the $$$x$$$ we delete is non-increasing.
It means we can solve this problem by dynamic programming. Let $$$dp_i$$$ represents when $$$\text{mex}(S)=i$$$, the minimum value of $$$m$$$.
Let $$$a_i$$$ represents the number of times $$$i$$$ appears in $$$S$$$, the transition is: $$$\forall j < i, dp_j \leftarrow dp_i + i \times (a_j - 1) + j$$$.
Time complexity: $$$O(n^2)$$$ per test case. (Moreover, you can use Convex Hull Optimisation to optimize dynamic programming, for $$$O(n)$$$ per test case)