Even More Odd Photos#11196

Even More Odd Photos

1 second

128 megabytes

Medium

Farmer John is yet again trying to take a photograph of his $n$ cows.

Each cow has an integer "breed ID" number in the range $1 \dots 100$ . Farmer John has a very peculiar idea in mind for his photo: he wants to partition all the cows into disjoint groups (in other words, place each cow in exactly one group) and then line up the groups so the sum of the breed IDs of the cows in the first group is even, the sum of the IDs in the second group is odd, and so on, alternating between even and odd.

What is the maximum possible number of groups Farmer John can form?

Input

The first line contains $n$ ( $2 \leq n \leq 1000$ 2 \le n \le 1000). The next line contains $n$ integers giving the breed IDs of the $n$ cows.

Output

Print the maximum possible number of groups in Farmer John's photo. It can be shown that at least one feasible grouping exists.

Examples

In this example, one way to form the maximum number ( $3$ ) of groups is as follows:

Group 1: 1 3
Group 2: 5 7 9
Group 3: 11 13

In this example, one way to form the maximum number ( $5$ ) of groups is as follows:

Group 1: 2
Group 2: 11
Group 3: 13 1
Group 4: 15
Group 5: 17 3

Example 1

Example 2