У Василия есть массив из $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$. За одно действие он может поменять местами два рядом стоящих элемента. Два элемента $$$a_i$$$ и $$$a_j$$$ называются рядом стоящими, если выполняется условие $$$|i - j| = 1$$$.
Василий просит вас посчитать минимальное количество действий для того, чтобы в массиве не было двух рядом стоящих элементов с одинаковой четностью.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество элементов в массиве Василия.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — описание массива Василия.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите минимальное количество операций или $$$-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
В первом тестовом примере подходит следующая последовательность операций:
- 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]$$$
