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:

  1. Takes a list of numbers as input.

  2. Prints the list.

  3. Removes all instances of the most common number in the list (in case of a draw, remove the largest number).

  4. 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.


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$.


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
1 2 1 4 4
CPU Time limit 2 seconds
Memory limit 1024 MB
Languages English, Íslenska
Bergur Snorrason and Atli Fannar Franklín
Source Forritunarkeppni Háskóla Íslands 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in