Rarest Insects

문제

There are $NN$ insects, indexed from $00$ to $N-1N\; -\; 1$, running around Pak Blangkon's house. Each insect has a type, which is an integer between $00$ and ${10}^{9}10^9$ inclusive. Multiple insects may have the same type.

Suppose insects are grouped by type. We define the cardinality of the most frequent insect type as the number of insects in a group with the most number of insects. Similarly, the cardinality of the rarestinsect type is the number of insects in a group with the least number of insects.

For example, suppose that there are $1111$ insects, whose types are $[5,7,9,11,11,5,0,11,9,100,9][5,\; 7,\; 9,\; 11,\; 11,\; 5,\; 0,\; 11,\; 9,\; 100,\; 9]$. In this case, the cardinality of the most frequent insect type is $33$. The groups with the most number of insects are type $99$ and type $1111$, each consisting of $33$ insects. The cardinality of the rarest insect type is $11$. The groups with the least number of insects are type $77$, type $00$, and type $100100$, each consisting of $11$ insect.

Pak Blangkon does not know the type of any insect. He has a machine with a single button that can provide some information about the types of the insects. Initially, the machine is empty. To use the machine, three types of operations can be performed:

1. Move an insect to inside the machine.
2. Move an insect to outside the machine.
3. Press the button on the machine.

Each type of operation can be performed at most $4000040\backslash ,000$ times.

Whenever the button is pressed, the machine reports the cardinality of the most frequent insect type, considering only insects inside the machine.

Your task is to determine the cardinality of the rarest insect type among all $NN$ insects in Pak Blangkon's house by using the machine. Additionally, in some subtasks, your score depends on the maximum number of operations of a given type that are performed (see Subtasks section for details).