У Sho есть массив \(a\) состоящий из \(n\) целых чисел. За одну операцию Sho может выбрать два различных индекса \(i\) и \(j\), после чего удалить из массива элементы \(a_i\) и \(a_j\).
Например, для массива \([2, 3, 4, 2, 5]\) Sho может выбрать индексы \(1\) и \(3\) и удалить соответствующие элементы из массива. После этой операции массив будет выглядеть так: \([3, 2, 5]\). Заметьте, что после любой операции длина массива уменьшится на два.
После нескольких операций у Sho остался массив, содержащий только различные числа. Также, он применил операции таким образом, что длина оставшегося массива максимальна из всех возможных.
Более формально, после всех операций массив Sho удовлетворяет двум следующим критериям:
- В массиве не существует таких пар индексов, что \(i < j\) и \(a_i = a_j\).
- Длина массива \(a\) максимальна.
Выведите длину оставшегося у Sho массива.
Выходные данные
Для каждого набора данных выведите единственное число — длину оставшегося массива. Помните, что в оставшемся массиве все элементы различны, а его длина максимальна.
Примечание
В первом наборе данных Sho может сделать следующие операции:
- Выбрать индексы \(1\) и \(5\). Тогда массив станет \([2, 2, 2, 3, 3, 3] \rightarrow [2, 2, 3, 3]\).
- Выбрать индексы \(1\) и \(4\). Тогда массив станет \([2, 2, 3, 3] \rightarrow [2, 3]\).
Финальный массив имеет длину
\(2\), так что ответом является
\(2\). Можно доказать, что Sho не может получить массив большей длины.
Во втором наборе данных Sho может сделать следующие операции:
- Выбрать индексы \(3\) и \(4\). Тогда массив станет \([9, 1, 9, 9, 1] \rightarrow [9, 1, 1]\).
- Выбрать индексы \(1\) и \(3\). Тогда массив станет \([9, 1, 1] \rightarrow [1]\).
Финальный массив имеет длину
\(1\), так что ответом является
\(1\). Можно доказать, что Sho не может получить массив большей длины.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
6
2 2 2 3 3 3
5
9 1 9 9 1
4
15 16 16 15
4
10 100 1000 10000
|
2
1
2
4
|