Maximum Odd Sum Pairs

Given an array of integers, you are to determine the maximum number of pairs you can form such that the sum of the two numbers in each pair is odd.

A pair has an odd sum if and only if one number is even and the other is odd. Thus, the maximum number of such pairs is given by:

$$ \text{max pairs} = \min(\text{count(odd)},\ \text{count(even)}) $$

For example, if the array is [1, 2, 3, 4, 5], there are 3 odd numbers (1, 3, 5) and 2 even numbers (2, 4), so the maximum number of pairs is \( \min(3,2)=2 \).

Your task is to compute this maximum number of pairs for a given list of integers.

inputFormat

The first line of input contains a single integer \( n \) representing the number of elements in the array.

The second line contains \( n \) integers separated by spaces.

outputFormat

Output a single integer representing the maximum number of pairs with odd sums that can be formed from the given array.

5
1 2 3 4 5

2