Question
Parity Shift
Ram has an array A of N non-negative integers. An array is considered aligned if each element’s evenness (odd or even) matches its index’s evenness, i.e., Ai % 2 == i % 2 for all i (0 ≤ i < N). He can exchange any two elements in one move. Find the fewest moves needed to align the array, or output -1 if it’s impossible.
Input
The first line of the input contains a single integer N.
The second line of the input contains N space-separated integers.
Constraints
1 ≤ N ≤ 105
1 ≤ Ai ≤ 109
The second line of the input contains N space-separated integers.
Constraints
1 ≤ N ≤ 105
1 ≤ Ai ≤ 109
Output
Print the fewest moves needed to align the array, or output -1 if it’s impossible.
Example
Sample Input
4
3 2 7 6
Sample Output
2
Explanation
In the first move, you can swap the elements with indices 0 and 1.
In the second move, you can swap the elements with indices 2 and 3.
4
3 2 7 6
Sample Output
2
Explanation
In the first move, you can swap the elements with indices 0 and 1.
In the second move, you can swap the elements with indices 2 and 3.