Вам дан массив \(a[0 \ldots n-1]\) длины \(n\), который состоит из неотрицательных целых чисел. Обратите внимание: массив нумеруется с нуля.
Назовём массив хорошим, если четность каждой позиции совпадает с четностью элемента в ней. Более формально, массив является хорошим, если для всех \(i\) (\(0 \le i \le n - 1\)) выполнено равенство \(i \bmod 2 = a[i] \bmod 2\), где \(x \bmod 2\) — остаток от деления \(x\) на 2.
Например, массивы [\(0, 5, 2, 1\)] и [\(0, 17, 0, 3\)] — хорошие, а массив [\(2, 4, 6, 7\)] — плохой, потому что для \(i=1\) четность \(i\) и \(a[i]\) различна: \(i \bmod 2 = 1 \bmod 2 = 1\), но \(a[i] \bmod 2 = 4 \bmod 2 = 0\).
За один ход вы можете взять любые два элемента массива и поменять их местами (эти элементы не обязательно соседние).
Найдите минимальное количество ходов, за которое можно сделать массив \(a\) хорошим, либо укажите, что это сделать невозможно.
Выходные данные
Для каждого набора тестовых данных выведите одно целое число — минимальное количество ходов, за которое можно сделать заданный массив \(a\) хорошим, или -1, если это сделать невозможно.
Примечание
В первом наборе тестовых данных в первый ход можно поменять местами элементы на позициях \(0\) и \(1\), а во второй ход поменять местами элементы на позициях \(2\) и \(3\).
Во втором наборе тестовых данных в первый ход надо поменять местами элементы на позициях \(0\) и \(1\).
В третьем наборе тестовых данных нельзя сделать массив хорошим.