CF1875D.Jellyfish and Mex

给定一个包含 $n$ 个非负整数的数组 $a_1, a_2, \dots, a_n$。

令 $m$ 为一个初始值为 $0$ 的变量，Jellyfish 将进行如下操作共 $n$ 次：

• 选择一个下标 $i$（$1 \leq i \leq |a|$），并从 $a$ 中删除 $a_i$。
• 将 $\operatorname{MEX}(a)^{\dagger}$ 加到 $m$ 上。

现在，Jellyfish 想知道，如果每一步都最优地进行操作，$m$ 的最终最小可能值是多少。

$^{\dagger}$ 数组的 MEX（minimum excluded）是指不属于该数组的最小非负整数。例如：

• $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 不在数组中。
• $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 在数组中，但 $2$ 不在。
• $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0$、$1$、$2$、$3$ 都在数组中，但 $4$ 不在。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 5000$），表示测试用例的数量。

每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示数组的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 10^9$），表示数组中的元素。

保证所有测试用例中 $n$ 的总和不超过 $5000$。

对于每组测试用例，输出一个整数，表示在最优操作下 $m$ 的最小值。

在第一个测试用例中，可以按如下顺序删除 $a$ 中的元素：$[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 [~]$。$m$ 的值为 $1+1+1+0+0+0+0+0=3$。

由 ChatGPT 4.1 翻译