Маленький Слоник любит играть с цветными карточками.
У него есть n карточек, каждая имеет ровно два цвета (цвет на передней стороне и цвет на задней стороне). Изначально все карточки лежат на столе передней стороной вверх. За один шаг Маленький Слоник может перевернуть на другую сторону любую карточку. Маленький Слоник считает набор карточек на столе веселым, если хотя бы половина карточек имеет одинаковый цвет (для каждой карточки рассматривается цвет стороны, которой она лежит вверх).
Помогите Маленькому Слонику найти минимальное количество шагов необходимых для превращения набора из n карточек в веселый.
Выходные данные
В единственной строке выведите единственное целое число — искомое минимальное количество шагов. Если превратить набор в веселый невозможно, выведите -1.
Примечание
В первом примере изначально лежат три карточки из цветами 4, 4, 7. Так как две из трех карточек имеют одинаковый цвет 4, менять ничего не нужно, поэтому ответ — 0.
Во втором примере можно перевернуть первую и четвертую карточки. После этого три из пяти карточек будут иметь цвет 7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 7
4 7
7 4
|
0
|
|
2
|
5
4 7
7 4
2 11
9 7
1 1
|
2
|