Question
Max Cards After Operations
You are given a collection of N cards, each with a number on it. In one move, you can pick any three cards, remove them, discard the largest and smallest numbers, and return the middle card to the collection. You repeat this process until all the remaining cards have unique numbers. Your task is to determine the maximum number of cards that can remain after performing any number of these operations (including possibly none).
Input
The first line of the input contains a single integer N.
The second line of the input contains N space-separated integers.
Constraints
N is an odd integer
1 ≤ N ≤ 105
1 ≤ Ai ≤ 109
The second line of the input contains N space-separated integers.
Constraints
N is an odd integer
1 ≤ N ≤ 105
1 ≤ Ai ≤ 109
Output
Print the highest number of cards that can remain after performing any number of operations (including possibly none).
Example
Sample Input
5
1 2 1 3 7
Sample Output
3
Explanation
In the first move, we choose the elements as 1, 2, 1.
We remove 2 (greatest element), one instance of 1(smallest element) and insert back 1(remaining element) to the deck.
This makes our array as [1, 3, 7]. No further operations required.
5
1 2 1 3 7
Sample Output
3
Explanation
In the first move, we choose the elements as 1, 2, 1.
We remove 2 (greatest element), one instance of 1(smallest element) and insert back 1(remaining element) to the deck.
This makes our array as [1, 3, 7]. No further operations required.