Alternating Group Partition

Farmer John is trying once again to take a photograph of his N cows (2 ≤ N ≤ 1000). Each cow has a breed ID, an integer in the range 1 to 100. Farmer John wants to partition all his cows into several disjoint groups (each cow must be in exactly one group) and then arrange these groups in a row such that the sum of breed IDs in the first group is even, the sum in the second group is odd, the third group is even, the fourth is odd, and so on (i.e. the parities alternate).

The twist is that the groups do not need to be contiguous in the original ordering; you can distribute the cows arbitrarily among the groups. For each group, you are allowed to use as few cows as possible to achieve the desired parity:

• For an even-sum group, you may either use one cow with an even breed ID or use two cows with odd breed IDs (since odd+odd yields even).
• For an odd-sum group, you must use at least one cow with an odd breed ID (a single odd number is odd).

Your task is to determine the maximum number of groups Farmer John can form following this alternating parity pattern.

Note: It is always allowed to choose the minimal number of cows needed for each group in order to maximize the total number of groups.

inputFormat

The first line contains a single integer N (2 ≤ N ≤ 1000), the number of cows.

The second line contains N integers, each between 1 and 100, representing the breed IDs of the cows.

outputFormat

Output a single integer, the maximum number of groups that can be formed.

sample

5
2 3 4 5 6

5