CF1806B.Mex Master
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an array a of length n . The score of a is the MEX † of [a1+a2,a2+a3,…,an−1+an] . Find the minimum score of a if you are allowed to rearrange elements of a in any order. Note that you are not required to construct the array a that achieves the minimum score.
† The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:
- The MEX of [2,2,1] is 0 , because 0 does not belong to the array.
- The MEX of [3,1,0,1] is 2 , because 0 and 1 belong to the array, but 2 does not.
- The MEX of [0,3,1,2] is 4 because 0 , 1 , 2 , and 3 belong to the array, but 4 does not.
输入格式
The first line contains a single integer t ( 1≤t≤104 ) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer n ( 2≤n≤2⋅105 ).
The second line of each test case contains n integers a1,a2,…,an ( 0≤ai≤2⋅105 ).
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 .
输出格式
For each test case, output the minimum score of a after rearranging the elements of a in any order.
输入输出样例
输入#1
3 2 0 0 3 0 0 1 8 1 0 0 0 2 0 3 0
输出#1
1 0 1
说明/提示
In the first test case, it is optimal to rearrange a as [0,0] , the score of this array is the MEX of [0+0]=[0] , which is 1 .
In the second test case, it is optimal to rearrange a as [0,1,0] , the score of this array is the MEX of [0+1,1+0]=[1,1] , which is 0 .