Longest Even Sum Subsequence

Given a sequence of n integers, find the length of the longest subsequence such that the sum of any two numbers in the subsequence is even.

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

Hint: For the sum of two numbers to be even, both numbers must be either even or odd. Therefore, the answer is the maximum of the number of even elements and the number of odd elements in the sequence.

inputFormat

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

The second line contains n space-separated integers, which are the elements of the sequence.

outputFormat

Output a single integer, the length of the longest subsequence such that for every pair of numbers in the subsequence, their sum is even.

## sample

5
1 2 3 4 5

3

</p>