|
Алиса и Боб играют в очередную игру на массиве a длины n. Алиса начинает с пустого массива c. Оба игрока ходят по очереди, причем Алиса начинает первой.
В свой ход Алиса выбирает один элемент из a, добавляет его в c, а затем удаляет из a.
В свой ход Боб выбирает один элемент из a, а затем удаляет его из a.
Игра заканчивается, когда массив a становится пустым. Счет игры определяется как MEX† элементов c. Алиса хочет максимизировать счет игры, а Боб — минимизировать его. Найдите итоговый счет игры, если оба игрока играют оптимально.
† 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≤t≤2⋅104) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных находится одно целое число n (1≤n≤2⋅105).
Вторая строка каждого набора входных данных содержит n целых чисел a1,a2,…,an (0≤ai<n).
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2⋅105.
Выходные данные
Для каждого набора входных данных найдите счет игры, если оба игрока играют оптимально.
|