Person in Charge

• SleepingCup

Problem Description

Today is Little Q's birthday, and he received $n$ cards as gifts. These cards belong to the popular "Duel Monsters," where the $i$-th card represents a monster with an attack power of $r_i$ and a defense power of $r_i$.

A game consists of several rounds. In each round, Little Q will choose a monster $i$ and another monster $j (i \neq j)$, then have monster $i$ attack monster $j$. If the attack power of monster $i$ is less than or equal to the defense power of monster $j$, nothing happens. Otherwise, monster $j$'s defense is broken, and monster $j$ exits the game and no longer participates in the remaining rounds. Each monster can at most initiate one attack during the entire game. The game ends when all remaining monsters have initiated their attacks.

Little Q wants to determine an attack sequence such that the number of remaining monsters at the end of the game is minimized.

Input Format

The first line of input contains a positive integer $n$, representing the number of cards.

The second line of input contains $n$ positive integers, where the $i$-th integer represents the attack and defense power $r_i$ of the $i$-th monster.

Output Format

Output a single integer representing the minimum number of remaining monsters at the end of the game.

Samples

5
1 2 3 1 2

2

10
136 136 136 2417 136 136 2417 136 136 136

8

Sample 1 Explanation

One optimal strategy is: In the first round, have monster 2 attack monster 1. In the second round, have monster 5 attack monster 4. In the third round, have monster 3 attack monster 5. At this point, all remaining monsters have initiated their attacks, and the game ends. It can be proven that no better attack sequence exists.

Sample 3

See the files duel/duel3.in and duel/duel3.ans in the contestant directory.

This sample satisfies $\forall 1 \le i \le n, r_i \le 2$.

Sample 4

See the files duel/duel4.in and duel/duel4.ans in the contestant directory.

Data Range

For all test data, it is guaranteed that: $1 \le n \le 10^5$, $1 \le r_i \le 10^5$.

Special Property A: Each $r_i$ is independently and uniformly randomly generated within the possible value range.