Peter has a sequence of A non-negative integers of length n. The numbers in the sequence are numbered starting from zero. Peter considers the sequence happy if the parity of each element of the sequence coincides with the parity of the number of the given element. Formally, this means that if for all i (0 <= i <= n - 1) the equality i mod 2 = a[i] mod 2, where x mod 2 is the remainder of dividing x by 2, then the sequence is lucky.
Peter wants to make his sequence happy, for this he takes any two elements and swaps them (the elements are not necessarily adjacent). Help Petya find the minimum number of moves in which he can make his sequence happy. If Petya fails to make the sequence happy, print -1.
Input
The program receives an integer as input in the first line n (1 <= n <= 40) — the size of the sequence A. Followed by a string containing n integers a0,a1 ,…,an−1 (0 <= ai < = 1000) — integer non-negative numbers of the sequence.
Output
For each test case, print one integer — the minimum number of moves required to make the given sequence A happy, or -1 if it is impossible.
Examples
| # |
Input |
Output |
| 1 |
4
3 2 7 6
|
2
|
| 2 |
1
7
|
-1
|
| 3 |
7
4 9 2 1 18 3 0
|
0
|