← 返回题目列表

Codeforces · 1875/D

D. 水母和墨西哥

中文机器翻译题面 查看原题

给你一个 $$$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(排除最小值)是不属于该数组的最小非负整数。例如:

- $$$[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$$$ 的最小值。

示例

输入 #1

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

输出 #1

3
0
2
7

注意

在第一个测试用例中,我们按以下顺序从 $$$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$$$。