Longest Even Sum Subsequence

Given an array of integers, determine the length of the longest subsequence (not necessarily contiguous) such that the sum of its elements is even.

The problem can be mathematically stated as follows:

Let \(A = [a_1, a_2, \ldots, a_n]\) be an array of integers. Find the maximum \(k\) (with \(0 \le k \le n\)) for which there exists a subsequence \(B\) of \(A\) with \(k\) elements such that \[ \sum_{b \in B} b \equiv 0 \pmod{2}. \]

If the total sum of the array is already even, then the entire array is a valid subsequence. Otherwise, removing a single odd element from an array with an odd total sum will yield an even sum (if such an element exists). If the array is empty, the answer is zero.

inputFormat

The input begins with an integer \(n\) (where \(0 \le n \le 10^5\)), the number of elements in the array. The next line contains \(n\) space-separated integers representing the elements of the array \(A\).

If \(n = 0\), the second line will be absent.

outputFormat

Output a single integer representing the length of the longest subsequence whose sum is even.

6
1 2 3 4 5 6

5