Вы и Нина играете в карточную игру. Для игры используется колода из \(2n\) карт. На каждой карте написано целое число от \(1\) до \(n\), и каждое из чисел от \(1\) до \(n\) встречается ровно на \(2\) картах. Кроме того, есть стол, на который размещаются карты во время игры (в начале игры стол пустой).
В начале игры эти \(2n\) карты распределяются между вами и Ниной так, что каждый игрок получает по \(n\) карт.
После этого вы и Нина поочередно делаете суммарно \(2n\) ходов, т. е. каждый делает по \(n\) ходов, начиная с вас. На каждом ходу:
- Игрок, чей сейчас ход, выбирает одну из карт в своей руке. Пусть \(x\) — число на выбранной карте.
- Игрок, чей сейчас ход, получает \(1\) очко, если на столе уже есть карта с числом \(x\) (в противном случае он не получает очков). Затем он кладет выбранную карту с числом \(x\) на стол.
Обратите внимание, что ходы делаются публично: каждый игрок может видеть все карты на столе в каждый момент времени.
Нина очень умная, поэтому она всегда выбирает карты оптимальным образом, чтобы максимизировать свой счет в конце игры (после \(2n\) раундов). Если у нее есть несколько оптимальных ходов, она выбирает ход, который минимизирует ваш счет в конце игры.
Более формально, Нина всегда делает ходы оптимальным образом, чтобы в первую очередь максимизировать свой счет в конце игры и во вторую очередь минимизировать ваш счет в конце игры.
Пусть в начале игры числа на ваших картах — \(a_1, a_2, \ldots, a_n\). Какое максимальное количество очков вы можете получить, делая свои ходы оптимальным образом?
Выходные данные
Для каждого тестового случая выведите одно целое число: максимальное количество очков, которое вы можете получить.
Примечание
В первом наборе входных данных на ваших картах написаны числа \(1\), \(1\), \(2\) и \(3\). На картах Нины написаны числа \(2\), \(3\), \(4\) и \(4\). Возможный ход игры:
- Вы выбираете одну из карт с числом \(1\) и кладете ее на стол.
- Нина выбирает одну из карт с числом \(4\) и кладет ее на стол.
- Вы выбираете карту с числом \(1\), получаете \(1\) очко и кладете выбранную карту на стол.
- Нина выбирает карту с числом \(4\), получает \(1\) очко и кладет выбранную карту на стол.
- Вы выбираете карту с числом \(2\) и кладете ее на стол.
- Нина выбирает карту с числом \(2\), получает \(1\) очко и кладет выбранную карту на стол.
- Вы выбираете карту с числом \(3\) и кладете ее на стол.
- Нина выбирает карту с числом \(3\), получает \(1\) очко и кладет выбранную карту на стол.
В конце игры вы набрали \(1\) очко, а Нина \(3\). Можно показать, что вы не можете набрать больше \(1\) очка, если Нина играет оптимальным образом, поэтому ответ \(1\).
Во втором тестовом случае, если оба игрока играют оптимальным образом, вы набираете \(2\) очка, а Нина — \(6\) очков.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
1 1 2 3
8
7 4 1 2 8 8 5 5
8
7 1 4 5 3 4 2 6
3
1 2 3
1
1
|
1
2
1
0
0
|