У Пети есть последовательность A
неотрицательных целых чисел длины n
. Числа в последовательности пронумерованы, начиная с нуля. Петя считает последовательность счастливой, если четность каждого элемента последовательности совпадает с четностью номера данного элемента. Формально это означает, что если для всех i
(0 <= i
<= n - 1) выполнено равенство i mod 2 = a[i] mod 2
, где x mod 2
- остаток от деления x
на 2, то последовательность является счастливой.
Петя хочет сделать свою последовательность счастливой, для этого он берет любые два элемента и меняет их местами (элементы не обязательно соседние). Помогите найти Пете минимальное количество ходов, за которое он сможет сделать свою последовательность счастливой. Если у Пети не получится сделать последовательность счастливой, выведите -1
.
Входные данные
Программа получает на вход в первой строке целое число n
(1 <= n <=
40) — размер последовательности A
. Далее следует строка, содержащая n
целых чисел a0,a1,…,an−1
(0 <= ai
<= 1000) — целые неотрицательные числа последовательности.
Выходные данные
Для каждого набора тестовых данных выведите одно целое число — минимальное количество ходов, за которое можно сделать заданную последовательность A
счастливой, или -1
, если это сделать невозможно.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
4
3 2 7 6
|
2
|
2 |
1
7
|
-1
|
3 |
7
4 9 2 1 18 3 0
|
0
|