Duel Monsters Attack Order

Today is Little Q's birthday and he has received n cards as a gift. Each card represents a Duel Monster whose attack and defense values are equal to r_i. The game is played in several rounds. In each round, Little Q selects one monster i (which has not attacked yet) and another monster j (with i ≠ j) that is still in the game, and makes monster i attack monster j.

The rules of an attack are as follows:

• If the attacker's attack is less than or equal to the defender's defense, i.e. if \(r_i \le r_j\), nothing happens.
• If \(r_i > r_j\), the defender's defense is broken and monster j is eliminated from the game.

Each monster is allowed to initiate an attack at most once. The game continues until every monster still in the game has already attacked. Little Q wants to decide an attack order so that the number of monsters remaining at the end is minimized. In other words, you need to choose a valid sequence of attacks that maximizes the number of eliminations, and then output the minimum number of survivors.

Note: Even if a monster is eliminated, it may have already used its one attack opportunity. Therefore, the optimal strategy is to pair monsters such that a monster with a strictly higher value eliminates a monster with a lower value. A valid strategy is to sort the monsters by their value \(r_i\) and then match the smallest available monster as the victim with the next monster that has a strictly larger value as the attacker. Each such pairing eliminates one monster.

The answer is given by:

[ \text{survivors} = n - \text{(maximum number of valid attack pairs)} ]

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of cards (monsters). The second line contains n integers r₁, r₂, ..., r_n (1 ≤ r_i ≤ 10⁹), where each r_i is the attack (and defense) value of the i-th monster.

outputFormat

Output a single integer, the minimum number of monsters that can remain in the game after arranging the attack order optimally.

sample

3
1 2 3

1