P9941 [USACO21JAN] Even More Odd Photos B

Farmer John is once again trying to take a photo of his $N$ cows ($2\le N\le 1000$). Each cow has an integer “breed ID” in the range $1\ldots 100$. Farmer John has a very strange idea for his photo: he wants to split all the cows into several disjoint groups (in other words, put each cow into exactly one group) and arrange these groups in a line, so that the sum of breed IDs in the first group is even, the sum in the second group is odd, and so on, alternating even and odd. What is the maximum number of groups Farmer John can make?

The first line contains $N$. The next line contains $N$ space-separated integers, the breed IDs of the $N$ cows.

Output the maximum number of groups in Farmer John’s photo. It can be proven that there is always at least one grouping plan that satisfies the requirements.

### Sample Explanation 1 In this sample, the following is one way to split into the maximum of three groups. Put 1 and 3 into the first group, 5, 7, and 9 into the second group, and 11 and 13 into the third group. ### Sample Explanation 2 In this sample, the following is one way to split into the maximum of five groups. Put 2 into the first group, 11 into the second group, 13 and 1 into the third group, 15 into the fourth group, and 17 and 3 into the fifth group. Translated by ChatGPT 5