Rarest Insects

There are $N$ insects, indexed from $0$ to $N - 1$, running around Pak Blangkon's house.
Each insect has a type, which is an integer between $0$ and $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 rarest insect type is the number of insects in a group with the least number of insects.

For example, suppose that there are $11$ insects, whose types are $[5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]$.
In this case, the cardinality of the most frequent insect type is $3$. The groups with the most number of insects are type $9$ and type $11$, each consisting of $3$ insects.
The cardinality of the rarest insect type is $1$. The groups with the least number of insects are type $7$, type $0$, and type $100$, each consisting of $1$ 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.
1. Move an insect to outside the machine.
1. Press the button on the machine.

Each type of operation can be performed at most $40\;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 $N$ 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).

Implementation Details

You should implement the following procedure:

int min_cardinality(int N)

• $N$: the number of insects.
• This procedure should return the cardinality of the rarest insect type among all $N$ insects in Pak Blangkon's house.
• This procedure is called exactly once.

The above procedure can make calls to the following procedures:

void move_inside(int i)

• $i$: the index of the insect to be moved inside the machine. The value of $i$ must be between $0$ and $N - 1$ inclusive.
• If this insect is already inside the machine, the call has no effect on the set of insects in the machine. However, it is still counted as a separate call.
• This procedure can be called at most $40\;000$ times.

void move_outside(int i)

• $i$: the index of the insect to be moved outside the machine. The value of $i$ must be between $0$ and $N - 1$ inclusive.
• If this insect is already outside the machine, the call has no effect on the set of insects in the machine. However, it is still counted as a separate call.
• This procedure can be called at most $40\;000$ times.

int press_button()

• This procedure returns the cardinality of the most frequent insect type, considering only insects inside the machine.
• This procedure can be called at most $40\;000$ times.
• The grader is not adaptive. That is, the types of all $N$ insects are fixed before min_cardinality is called.

Example

Consider a scenario in which there are $6$ insects of types $[5, 8, 9, 5, 9, 9]$ respectively.
The procedure min_cardinality is called in the following way:

min_cardinality(6)

The procedure may call move_inside, move_outside, and press_button as follows.

At this point, there is sufficient information to conclude that the cardinality of the rarest insect type is $1$.
Therefore, the procedure min_cardinality should return $1$.

In this example, move_inside is called $7$ times, move_outside is called $1$ time, and press_button is called $6$ times.

Constraints

• $2 \le N \le 2000$

If in any of the test cases, the calls to the procedures move_inside, move_outside, or press_button do not conform to the constraints described in Implementation Details, or the return value of min_cardinality is incorrect, the score of your solution for that subtask will be $0$.

Let $q$ be the maximum of the following three values: the number of calls to move_inside, the number of calls to move_outside, and the number of calls to press_button.

In this subtask, you can obtain a partial score.
Let $m$ be the maximum value of $\frac{q}{N}$ across all test cases in this subtask.
Your score for this subtask is calculated according to the following table:

Sample Grader

Let $T$ be an array of $N$ integers where $T[i]$ is the type of insect $i$.

The sample grader reads the input in the following format:

• line $1$: $N$
• line $2$: $T[0] \; T[1] \; \ldots \; T[N - 1]$

If the sample grader detects a protocol violation, the output of the sample grader is Protocol Violation: <MSG>, where <MSG> is one of the following:

• invalid parameter: in a call to move_inside or move_outside, the value of $i$ is not between $0$ and $N - 1$ inclusive.
• too many calls: the number of calls to any of move_inside, move_outside, or press_button exceeds $40\;000$.

Otherwise, the output of the sample grader is in the following format:

• line $1$: the return value of min_cardinality
• line $2$: $q$

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Rarest Insects)

There are $N$ insects, indexed from $0$ to $N - 1$, running around Pak Blangkon's house.
Each insect has a type, which is an integer between $0$ and $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 rarest insect type is the number of insects in a group with the least number of insects.

For example, suppose that there are $11$ insects, whose types are $[5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]$.
In this case, the cardinality of the most frequent insect type is $3$. The groups with the most number of insects are type $9$ and type $11$, each consisting of $3$ insects.
The cardinality of the rarest insect type is $1$. The groups with the least number of insects are type $7$, type $0$, and type $100$, each consisting of $1$ 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.
1. Move an insect to outside the machine.
1. Press the button on the machine.

Each type of operation can be performed at most $40\;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 $N$ 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).

Implementation Details

You should implement the following procedure:

int min_cardinality(int N)

• $N$: the number of insects.
• This procedure should return the cardinality of the rarest insect type among all $N$ insects in Pak Blangkon's house.
• This procedure is called exactly once.

The above procedure can make calls to the following procedures:

void move_inside(int i)

• $i$: the index of the insect to be moved inside the machine. The value of $i$ must be between $0$ and $N - 1$ inclusive.
• If this insect is already inside the machine, the call has no effect on the set of insects in the machine. However, it is still counted as a separate call.
• This procedure can be called at most $40\;000$ times.

void move_outside(int i)

• $i$: the index of the insect to be moved outside the machine. The value of $i$ must be between $0$ and $N - 1$ inclusive.
• If this insect is already outside the machine, the call has no effect on the set of insects in the machine. However, it is still counted as a separate call.
• This procedure can be called at most $40\;000$ times.

int press_button()

• This procedure returns the cardinality of the most frequent insect type, considering only insects inside the machine.
• This procedure can be called at most $40\;000$ times.
• The grader is not adaptive. That is, the types of all $N$ insects are fixed before min_cardinality is called.

Example

Consider a scenario in which there are $6$ insects of types $[5, 8, 9, 5, 9, 9]$ respectively.
The procedure min_cardinality is called in the following way:

min_cardinality(6)

The procedure may call move_inside, move_outside, and press_button as follows.

At this point, there is sufficient information to conclude that the cardinality of the rarest insect type is $1$.
Therefore, the procedure min_cardinality should return $1$.

In this example, move_inside is called $7$ times, move_outside is called $1$ time, and press_button is called $6$ times.

Constraints

• $2 \le N \le 2000$

If in any of the test cases, the calls to the procedures move_inside, move_outside, or press_button do not conform to the constraints described in Implementation Details, or the return value of min_cardinality is incorrect, the score of your solution for that subtask will be $0$.

Let $q$ be the maximum of the following three values: the number of calls to move_inside, the number of calls to move_outside, and the number of calls to press_button.

In this subtask, you can obtain a partial score.
Let $m$ be the maximum value of $\frac{q}{N}$ across all test cases in this subtask.
Your score for this subtask is calculated according to the following table:

Sample Grader

Let $T$ be an array of $N$ integers where $T[i]$ is the type of insect $i$.

The sample grader reads the input in the following format:

• line $1$: $N$
• line $2$: $T[0] \; T[1] \; \ldots \; T[N - 1]$

If the sample grader detects a protocol violation, the output of the sample grader is Protocol Violation: <MSG>, where <MSG> is one of the following:

• invalid parameter: in a call to move_inside or move_outside, the value of $i$ is not between $0$ and $N - 1$ inclusive.
• too many calls: the number of calls to any of move_inside, move_outside, or press_button exceeds $40\;000$.

Otherwise, the output of the sample grader is in the following format:

• line $1$: the return value of min_cardinality
• line $2$: $q$

Execution limits

Your solution will have 2.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "insects.h"

int min_cardinality(int N) {
  return 0;
}

参考代码

#include "insects.h"

int min_cardinality(int N) {
  return 0;
}

请将你的实现写入 submission.cpp（可沿用上面的框架与题目头文件）。判题时你的代码会与题目自带的 manager / grader 一起编译链接，并按题目规定的协议通信。

本题为交互题：你的程序需与题目自带的 manager 进程通信（按题目约定经标准输入输出或命名管道），无需自行读取测试数据。

由 manager 进程打印判定结果，无需自行写出答案。

include "insects.h"

int min_cardinality(int N) {
return 0;
}