Вам задан массив \(a\) длины \(n\), состоящий из целых чисел. Вы можете применять следующую операцию, состоящую из нескольких шагов, над массивом \(a\) ноль или более раз:
- вы выбираете два различных числа в массиве \(a_i\) и \(a_j\);
- вы удаляете \(i\)-й и \(j\)-й элементы из массива.
Например, если \(n=6\) и \(a=[1, 6, 1, 1, 4, 4]\), то вы можете произвести следующую последовательность операций:
- выбираем \(i=1, j=5\). Массив \(a\) становится равным \([6, 1, 1, 4]\);
- выбираем \(i=1, j=2\). Массив \(a\) становится равным \([1, 4]\).
Каким может быть минимальный размер массива после применения к нему некоторой последовательности операций?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальный возможный размер массива после применения к нему некоторой последовательности операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
6
1 6 1 1 4 4
2
1 2
2
1 1
5
4 5 4 5 4
6
2 3 2 1 3 1
|
0
0
2
1
0
|