Question
Triad Trim
Bob is given an array A of size N.
In one move, he can select any 3 elements:
- remove them
- discard the largest and smallest, and
- return the remaining element to the array.
He repeats this until all elements are unique.
Find the maximum possible number of elements that can remain after any number of operations (including 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 maximum possible number of elements that can remain after any number of operations (including 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.