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

A game consists of several rounds. In each round, Little Q chooses a monster $i$ and another monster $j$ ($i \neq j$), and has monster $i$ attack monster $j$. At this point, if the attack power of monster $i$ is less than or equal to the defense power of monster $j$, nothing happens; otherwise, the defense of monster $j$ is broken, and monster $j$ exits the game and no longer participates in the remaining rounds. Each monster can initiate an attack at most once during the entire game. The game ends when all monsters that have not yet exited the game have initiated an attack.

Little Q wants to determine an attack sequence such that the number of monsters remaining in the game when it ends is minimized.

Input

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

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

Output

Output a single integer representing the minimum number of monsters remaining in the game when it ends.

Examples

Input 1

5
1 2 3 1 2

Output 1

2

Note 1

One optimal strategy is: in the first round, let the 2nd monster attack the 1st monster; in the second round, let the 5th monster attack the 4th monster; in the third round, let the 3rd monster attack the 5th monster. At this point, all monsters that have not exited the game have performed an attack, and the game ends. It can be proven that there is no better attack sequence.

Input 2

10
136 136 136 2417 136 136 2417 136 136 136

Output 2

8

Examples 3

See duel/duel3.in and duel/duel3.ans in the contestant directory. This sample satisfies $\forall 1 \le i \le n, r_i \le 2$.

Examples 4

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

Constraints

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

Special Property A: It is guaranteed that each $r_i$ is generated independently and uniformly at random within the possible range.