Ушан решил сыграть в карточную игру. У него есть колода, состоящая из
N съедобных карт. На
i-й карте сверху написано целое число
Ai. Ушан выполняет описанную ниже операцию ноль или более раз, так что значения, записанные на оставшихся карточках, будут попарно различны.
Найдите максимально возможное количество оставшихся карт. Здесь
N нечетное, что гарантирует сохранение хотя бы одной карты.
Операция: вынуть из колоды три произвольные карты. Из этих трех карт съешьте две: одну с наибольшим значением, а другую с наименьшим значением. Затем верните оставшуюся одну карту в колоду.
Входные данные
В первой строке записано нечетное число
N (
\(3<=N<=10^5\)). Во второй строке записаны
N чисел
Ai (
\(1<=A_i<=10^5\))
Выходные данные
Выведите максимально возможное количество оставшихся карт.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
5
1 2 1 3 7 |
3 |
Оптимальное решение - выполнить операцию один раз, вынув две карты с 1 и одну карту с 2. Одна карта с 1 и другая с 2 будут съедены, а оставшаяся карта с 1 будет возвращена в колоду.
Тогда значения, написанные на оставшихся картах в колоде, будут попарно различными: 1, 3 и 7. |
| 2 |
15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1 |
7 |
|