Wushan decided to play a card game. He has a deck of
N edible cards. The
ith card has an integer
Ai written on top. Wushan performs the operation described below zero or more times, so that the values written on the remaining cards will be pairwise different.
Find the maximum possible number of remaining cards. Here,
N is odd, which ensures that at least one card is saved.
Operation: draw three random cards from the deck. Of these three cards, eat two: one with the highest value and the other with the lowest value. Then return the remaining one card to the deck.
Input
The first line contains an odd number
N (
\(3<=N<=10^5\)). The second line contains
N numbers
Ai (
\(1<=A_i<= 10^5\))
Imprint
Output the maximum possible number of remaining cards.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
5
1 2 1 3 7
| 3 |
The optimal solution is to perform the operation once, drawing two cards from 1 and one card from 2. One card from 1 and the other from 2 will be eaten, and the remaining card with 1 will be returned to the deck.
Then the values written on the remaining cards in the deck will be pairwise different: 1, 3 and 7. |
| 2 |
15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1
| 7 |
|