Вам задано \(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\) фишек в одну координату.
Примечание
В первом тестовом примере вам необходимо переместить первую фишку на \(2\) вправо и вторую фишку на \(1\) вправо или переместить третью фишку на \(2\) влево и вторую фишку на \(1\) влево, таким образом ответ равен \(1\).
Во втором тестовом примере вам необходимо передвинуть две фишки с координатами \(3\) на \(1\) влево, таким образом ответ равен \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4 8 6 3 12 9
|
9 3 6 12 4 8
|
|
2
|
4
42 28 84 126
|
126 42 84 28
|
|
3
|
2
1000000000000000000 3000000000000000000
|
3000000000000000000 1000000000000000000
|