给定一个长度为 n 的数组 a,a 的分数是新集合 b = [a_1+a_2,a_2+a_3,…,a_{n−1}+a_n] , , 的 MEX。
现在你能以任意顺序重新排列 a 的元素,请你找到 a 的最小分数,您不需要构造实现最小分数的数组 a。
数组的 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 不属于数组。
每个测试用例的第一行包含一个整数 n (2≤n≤2*10^5) 。
每个测试用例的第二行包含 n 个整数 a1,a2,…,an , , (0≤ai≤2*10^5) 。
它保证所有测试用例的 n 和不超过 2*10^5 。
对于每个测试用例,在以任意顺序重新排列 a 的元素后,输出 a 的最小分数。
输入样例1
8 1 0 0 0 2 0 3 0
输出样例1
1
输入样例2
3 0 0 1
输出样例2
0