CF1943A MEX Game 1

Alice and Bob play yet another game on an array $ a $ of size $ n $ . Alice starts with an empty array $ c $ . Both players take turns playing, with Alice starting first. On Alice's turn, she picks one element from $ a $ , appends that element to $ c $ , and then deletes it from $ a $ . On Bob's turn, he picks one element from $ a $ , and then deletes it from $ a $ . The game ends when the array $ a $ is empty. Game's score is defined to be the MEX $ ^\dagger $ of $ c $ . Alice wants to maximize the score while Bob wants to minimize it. Find game's final score if both players play optimally. $ ^\dagger $ The $ \operatorname{MEX} $ (minimum excludant) of an array of integers is defined as the smallest non-negative integer which does not occur in the array. For example: - 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.

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 2 \cdot 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i < n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, find game's score if both players play optimally.

In the first test case, a possible game with a score of $ 2 $ is as follows: 1. Alice chooses the element $ 1 $ . After this move, $ a=[0,0,1] $ and $ c=[1] $ . 2. Bob chooses the element $ 0 $ . After this move, $ a=[0,1] $ and $ c=[1] $ . 3. Alice chooses the element $ 0 $ . After this move, $ a=[1] $ and $ c=[1,0] $ . 4. Bob chooses the element $ 1 $ . After this move, $ a=[\,] $ and $ c=[1,0] $ . At the end, $ c=[1,0] $ , which has a MEX of $ 2 $ . Note that this is an example game and does not necessarily represent the optimal strategy for both players.