Farmer John is photographing N of his cows (2≤N≤1000).
Each cow has an integer - "Breed ID" in the range 1*100. FD split all cows into disjoint groups (in other words, put each cow in exactly one group) and then arrange the groups so that the sum of the "Breed ID" cows in the first group were even, in the second - odd, etc., alternating even and odd.
What is the maximum number of groups that a FD can form?
Input
The first line of input contains the number N. The next line contains N space-separated integers representing the "breed ID".
Imprint
The maximum possible number of groups in the PD photo. It can be proved that there will always be at least one group.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
7
1 3 5 7 9 11 13
|
3 |
In this example, one way to form the maximum number (3) of groups is as follows:
1 group: 1 3
Group 2: 5 7 9
3rd group: 11 13 |
| 2 |
7
11 2 17 13 1 15 3
|
5 |
In this example, one way to form the maximum number (5) of groups is as follows: 1 group: 2
Group 2: 11
3rd group: 13 1
4th group: 15
5th group: 17 3. |