A. MEX игра - 1
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в очередную игру на массиве $$$a$$$ длины $$$n$$$. Алиса начинает с пустого массива $$$c$$$. Оба игрока ходят по очереди, причем Алиса начинает первой.

В свой ход Алиса выбирает один элемент из $$$a$$$, добавляет его в $$$c$$$, а затем удаляет из $$$a$$$.

В свой ход Боб выбирает один элемент из $$$a$$$, а затем удаляет его из $$$a$$$.

Игра заканчивается, когда массив $$$a$$$ становится пустым. Счет игры определяется как MEX$$$^\dagger$$$ элементов $$$c$$$. Алиса хочет максимизировать счет игры, а Боб — минимизировать его. Найдите итоговый счет игры, если оба игрока играют оптимально.

$$$^\dagger$$$ $$$\operatorname{MEX}$$$ (minimum excludant) массива целых чисел определяется как наименьшее целое неотрицательное число, которое не встречается в массиве. Например:

  • MEX массива $$$[2,2,1]$$$ равен $$$0$$$, потому что $$$0$$$ не принадлежит массиву.
  • MEX массива $$$[3,1,0,1]$$$ равен $$$2$$$, потому что $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ — нет.
  • MEX массива $$$[0,3,1,2]$$$ равен $$$4$$$, потому что $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ принадлежат массиву, а $$$4$$$ — нет.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных находится одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < n$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных найдите счет игры, если оба игрока играют оптимально.

Пример
Входные данные
3
4
0 0 1 1
4
0 1 2 3
2
1 1
Выходные данные
2
1
0
Примечание

В первом наборе входных данных возможная игра со счетом $$$2$$$ выглядит следующим образом:

  1. Алиса выбирает элемент $$$1$$$. После этого хода $$$a=[0,0,1]$$$ и $$$c=[1]$$$.
  2. Боб выбирает элемент $$$0$$$. После этого хода $$$a=[0,1]$$$ и $$$c=[1]$$$.
  3. Алиса выбирает элемент $$$0$$$. После этого хода $$$a=[1]$$$ и $$$c=[1,0]$$$.
  4. Боб выбирает элемент $$$1$$$. После этого хода $$$a=[\,]$$$ и $$$c=[1,0]$$$.

В конце массив $$$c=[1,0]$$$, и его MEX равен $$$2$$$. Обратите внимание, что это пример игры и не обязательно представляет собой оптимальную стратегию для обоих игроков.