A. Перемещение фишек
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано $$$n$$$ фишек на числовой прямой. $$$i$$$-я фишка располагается в целочисленной координате $$$x_i$$$. Некоторые фишки могут иметь одинаковые координаты.

Вы можете совершать любой из следующих двух типов ходов любое (возможно, нулевое) количество раз над любой фишкой:

  • Переместить фишку $$$i$$$ на $$$2$$$ влево или на $$$2$$$ вправо бесплатно (то есть заменить текущую координату $$$x_i$$$ на $$$x_i - 2$$$ или $$$x_i + 2$$$);
  • переместить фишку $$$i$$$ на $$$1$$$ влево или на $$$1$$$ вправо и заплатить одну монету за этот ход (то есть заменить текущую координату $$$x_i$$$ на $$$x_i - 1$$$ или $$$x_i + 1$$$).

Заметьте, что разрешается перемещать фишки в любые целочисленные координаты, включая нулевую и отрицательные.

Ваша задача — найти минимальное суммарное количество монет, необходимое для того, чтобы переместить все $$$n$$$ фишек в одну координату (то есть после какой-то последовательности ходов все $$$x_i$$$ должны быть равны).

Входные данные

Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество фишек.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^9$$$), где $$$x_i$$$ равно координате $$$i$$$-й фишки.

Выходные данные

Выведите одно целое число — минимальное суммарное количество монет, необходимое для того, чтобы переместить все $$$n$$$ фишек в одну координату.

Примеры
Входные данные
3
1 2 3
Выходные данные
1
Входные данные
5
2 2 2 3 3
Выходные данные
2
Примечание

В первом тестовом примере вам необходимо переместить первую фишку на $$$2$$$ вправо и вторую фишку на $$$1$$$ вправо или переместить третью фишку на $$$2$$$ влево и вторую фишку на $$$1$$$ влево, таким образом ответ равен $$$1$$$.

Во втором тестовом примере вам необходимо передвинуть две фишки с координатами $$$3$$$ на $$$1$$$ влево, таким образом ответ равен $$$2$$$.