У Василия есть массив из \(n\) целых чисел \(a_1, a_2, \dots, a_n\). За одно действие он может поменять местами два рядом стоящих элемента. Два элемента \(a_i\) и \(a_j\) называются рядом стоящими, если выполняется условие \(|i - j| = 1\).
Василий просит вас посчитать минимальное количество действий для того, чтобы в массиве не было двух рядом стоящих элементов с одинаковой четностью.
Выходные данные
Для каждого набора входных данных выведите минимальное количество операций или \(-1\), если в любом случае в массиве будет два рядом стоящих числа с одинаковой четностью.
Примечание
В первом тестовом примере подходит следующая последовательность операций:
- swap(2, 3). Массив после применения операции: \([6, 1, 6]\)
Во втором тестовом примере в массиве изначально отсутствуют два рядом стоящих элемента с одинаковой четностью.
В третьем тестовом примере подходит следующая последовательность операций:
- swap(3, 4). Массив после применения операции: \([1, 1, 2, 1, 2, 2]\)
- swap(2, 3). Массив после применения операции: \([1, 2, 1, 1, 2, 2]\)
- swap(4, 5). Массив после применения операции: \([1, 2, 1, 2, 1, 2]\)
В четвертом тестовом примере требуемых условий добиться невозможно.
В пятом тестовом примере подходит следующая последовательность операций:
- swap(2, 3). Массив после применения операции: \([6, 3, 2, 4, 5, 1]\)
- swap(4, 5). Массив после применения операции: \([6, 3, 2, 5, 4, 1]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
6 6 1
1
9
6
1 1 1 2 2 2
2
8 6
6
6 2 3 4 5 1
|
1
0
3
-1
2
|