Longest Special Subsequence

You are given an array of n integers. Your task is to find the length of the longest special subsequence.

A subsequence is defined as special if the number of even elements in it satisfies the condition \[ \text{even_count} \bmod 2 = 0 \] which means the subsequence contains an even number of even numbers. Note that if the subsequence consists entirely of odd numbers, it is automatically special because 0 is even.

Examples:

• For the array [4, 2, 5, 3, 6], the entire array has 3 even numbers. By removing one element (any element) the condition will be met, so the answer is 4.
• For the array [1, 3, 5], there are no even numbers, hence the subsequence is special and the answer is 3.
• For the array [2, 4, 6, 8], the subsequence is already special with 4 even numbers, so the answer is 4.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of elements in the array.

The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer representing the length of the longest special subsequence.

5
4 2 5 3 6

4