Maximizing Good Pairs

Given an array of n integers, your task is to form as many pairs as possible such that the sum of each pair is even. A pair is considered good if the sum of the pair is even. Recall that the sum of two numbers is even if both numbers are even or both numbers are odd. Each element from the array can be used in at most one pair.

Your goal is to find the maximum number of good pairs that can be formed from the given array.

Note: Read the input from stdin and output the result to stdout.

inputFormat

The input consists of two lines. The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Print a single integer which is the maximum number of good pairs that can be formed, where each pair's sum is even.## sample

4
2 4 6 8

2