Question
Maximize Unique Elements
You have an array A of size N. In a single operation, you can select any three elements from the array, remove them, and then out of these three integers, you discard the largest and smallest, reinserting the middle element back into the array. You continue performing this operation until all remaining elements in the array are unique. What is the maximum number of elements that can remain in the array after completing any number of operations (including potentially not performing any operations at all)?
Input
The first line of the input contains a single integer N.
The second line of the input contains N space-seperated integers.
Constraints:
N is an odd integer
1 ≤ N ≤ 105
1 ≤ Ai ≤ 109
The second line of the input contains N space-seperated integers.
Constraints:
N is an odd integer
1 ≤ N ≤ 105
1 ≤ Ai ≤ 109
Output
Print the maximum possible count of the remaining cards after any number of operations (possibly zero).
Example
Sample Input
5
1 2 1 3 7
Sample Output
3
Explaination
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
Explaination
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.