Алиса и Боб играют в очередную игру на массиве \(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\) — нет.
Выходные данные
Для каждого набора входных данных найдите счет игры, если оба игрока играют оптимально.
Примечание
В первом наборе входных данных возможная игра со счетом \(2\) выглядит следующим образом:
- Алиса выбирает элемент \(1\). После этого хода \(a=[0,0,1]\) и \(c=[1]\).
- Боб выбирает элемент \(0\). После этого хода \(a=[0,1]\) и \(c=[1]\).
- Алиса выбирает элемент \(0\). После этого хода \(a=[1]\) и \(c=[1,0]\).
- Боб выбирает элемент \(1\). После этого хода \(a=[\,]\) и \(c=[1,0]\).
В конце массив \(c=[1,0]\), и его MEX равен \(2\). Обратите внимание, что это пример игры и не обязательно представляет собой оптимальную стратегию для обоих игроков.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
0 0 1 1
4
0 1 2 3
2
1 1
|
2
1
0
|