Longest Even Sum Subsequence

You are given a sequence of n integers. Your task is to find the length of the longest subsequence such that:

• The subsequence is non-decreasing.
• The sum of its elements is an even number.

The subsequence can be obtained by reordering the given list in non-decreasing order and then selecting some of the elements (not necessarily contiguous) that yield an even sum. In this problem, a straightforward strategy is to sort the array and pick all elements that are even, since the sum of only even numbers is even. Formally, given an array \( A = [a_1, a_2, \dots, a_n] \), the answer is the number of elements \( x \) in the sorted array for which \( x \equiv 0 \pmod{2} \).

Note: In some variants, one might consider mixing odd numbers such that their count is even. However, for this problem the intended solution is to consider only the even numbers.

inputFormat

The first line of input contains a single integer \( n \) representing the number of elements in the array. The second line contains \( n \) space-separated integers representing the elements of the array \( A \).

For example:

6
1 2 3 4 5 6

outputFormat

Output a single integer representing the length of the longest non-decreasing subsequence (derived from reordering the array) whose sum is even.

For example, given the input above, the output should be 3.

## sample

6
1 2 3 4 5 6

3