Longest Even Sum Subsequence

You are given an array of n integers. Your task is to determine the length of the longest subsequence whose sum is even.

Let \(a_1, a_2, \dots, a_n\) be the elements of the array and \(S = \sum_{i=1}^{n}a_i\). If \(S\) is even then the entire array is a valid subsequence; otherwise, by removing one odd element (if any exists), the sum becomes even. Therefore, the answer will be \(n\) if \(S\) is even, and \(n-1\) if \(S\) is odd.

Note: A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

inputFormat

Input is read from standard input. The first line contains an integer n denoting the number of elements in the array. The second line contains n space-separated integers representing the array elements.

outputFormat

Output to standard output a single integer which is the length of the longest subsequence with an even sum.

5
1 3 5 7 9

4