← 返回题目列表

Codeforces · 2224/B

B. 芝利和梅克斯和马克斯

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

在荒野深处,Zhily 和 Jily 发现了一个神秘的数字序列。序列的每个前缀都有一个重要的特征值,称为 mex 和 max。通过重新排列顺序,可以产生特殊的魔法。

给定一个由 $$$n$$$ 个非负整数组成的数组 $$$a$$$。您可以任意重新排列它。

求 MEX$$$^{\text{*}}$$$ 和所有前缀的最大值之和的最大可能值。形式上,您需要最大化以下表达式:$$$\sum\limits_{i=1}^n (\operatorname{mex}(a_1,a_2,\cdots,a_i)+\max(a_1,a_2,\cdots,a_i))$$$。

$$$^{\text{*}}$$$整数集合 $$$c_1, c_2, \ldots, c_k$$$ 的最小排除 (MEX) 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\cdots,a_n$$$ ($$$0\leq a_i \leq 10^9$$$) — 数组 $$$a$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,在新行上输出最大总和。

示例

输入
复制

5
5
0 0 0 0 0
2
0 1
5
1 1 1 1 0
6
1 1 4 5 1 4
1
1000000000

输出
复制

5
4
13
30
1000000000

注意

在第一个测试用例中,无论您如何重新排列 $$$a$$$,每个前缀的 MEX 和最大值将始终分别为 $$$1$$$ 和 $$$0$$$。

在第三个测试用例中,您可以将 $$$a$$$ 重新排列为 $$$[0,1,1,1,1]$$$,这样 $$$\sum\limits_{i=1}^n (\operatorname{mex}(a_1,a_2,\cdots,a_i)+\max(a_1,a_2,\cdots,a_i))=(1+0)+(2+1)+(2+1)+(2+1)+(2+1)=13$$$。可以证明这是最优解。