题目描述

给定一个长度为 $n$ 的数组 $a$。数组 $a$ 的得分定义为 $[a_1+a_2, a_2+a_3, \ldots, a_{n-1}+a_n]$ 的 MEX $^{\dagger}$。你可以任意重排 $a$ 的元素，求 $a$ 的最小得分。注意，你不需要构造出能够达到最小得分的数组 $a$。

$^{\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\le t\le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\le n\le 2\cdot10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 2\cdot 10^5$）。

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

输出格式

对于每个测试用例，输出重排 $a$ 后能够得到的最小得分。

说明/提示

在第一个测试用例中，最优的重排方式是 $[0,0]$，此时数组的得分为 $[0+0]=[0]$ 的 MEX，即 $1$。

在第二个测试用例中，最优的重排方式是 $[0,1,0]$，此时数组的得分为 $[0+1,1+0]=[1,1]$ 的 MEX，即 $0$。

由 ChatGPT 4.1 翻译

样例

3
2
0 0
3
0 0 1
8
1 0 0 0 2 0 3 0

1
0
1