Problem C
Reiknirit
As a final project in the course Þróun Hugbúnaðar (e. Software Development) Þórður decided to write a program serving a very important purpose. His program is an implementation of the following pseudocode:
-
Takes a list of numbers as input.
-
Prints the list.
-
Removes all instances of the most common number in the list (in case of a draw, remove the largest number).
-
Repeat $2$ and $3$ until the list is empty.
For example, if the program gets the list $[1, 2, 1, 4, 4]$ it will print $‘1\ 2\ 1\ 4\ 4’$, then $‘1\ 2\ 1’$ and lastly $‘2’$. When Þórður told his friend Garðar about this program, Garðar told him that in the worst case scenario the size of the output could grow proportional to the square of the size of the input. This scared Þórður since he wanted to show the output of the program when he presents it, but if the output gets too big it won’t fit on the slides in the presentation. Thus he turns to you for assistance. Given a list of numbers, deduce how many numbers Þórður’s program will print.
Input
The first line of the input contains one positive integer $1 \leq n \leq 10^6$. The second and last line of the input contains $n$ integers, the $i$-th of which, $e_ i$, satisfies $1 \leq e_ i \leq 10^9$.
Output
The only line of the output should contain the number of numbers that Þórður’s program will print if given the numbers $e_ i$ in the input as input.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 2 1 4 4 |
9 |
