#include "insects.h"
#include <bits/stdc++.h>
using namespace std; 
const int N = 2e3 + 5; 

// 最多问 3n 次询问
int n, m, k, id[N], cnt; 
vector<int> arr; 
bool in[N]; 
mt19937 Rand(time(0)); 

void Move_inside(int x) { move_inside(id[x] - 1); }
void Move_outside(int x) { move_outside(id[x] - 1); }
bool check(int x) { // 最罕见的昆虫是否能 >= x
    cnt = n; 
    for (int i : arr) {
        Move_inside(i); in[i] = 1; 
        if (press_button() > x) {
            Move_outside(i), in[i] = 0, --cnt; 
            if (cnt < k * x) {
                for (int i : arr)
                    if (in[i]) Move_outside(i), in[i] = 0; 
                return 0; 
            }
        }
    }
    if (cnt == k * x) {
        vector<int> newarr; 
        for (int i : arr)
            if (in[i]) newarr.emplace_back(i); 
        arr = newarr; 
    }
    return cnt == k * x; 
}
int min_cardinality(int N) {
    n = N; 
    k = n; 
    for (int i = 1; i <= n; ++i) id[i] = i; 
    shuffle(id + 1, id + n + 1, Rand);  
    for (int i = 1; i <= n; ++i) {
        Move_inside(i); 
        if (press_button() > 1) Move_outside(i), --k, arr.emplace_back(i); 
    }

    // 最罕见的出现次数是 1，当且仅当什么时候？
    int L = 0, R = n / k + 1; // [2, n / k]

    while (L + 1 != R) {
        int mid = L + R >> 1; 
        if (check(mid)) L = mid; 
        else R = mid; // 最罕见的昆虫一定 < mid
    }
    return L; 
}

// 我们可以知道的信息：

// n 次代价知道昆虫种类数 k
// n 次代价知道最常见的昆虫基数

// 那么最罕见的昆虫的基数至多是 n / k
// 直接扫，