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

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

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

int min_cardinality(int N) {
    n = N; 
    k = n; 
    for (int i = 1; i <= n; ++i) always_no[i] = 0; 
    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 = 1, R = n / k + 1; // [2, n / k]

    while (L + 1 != R && L < R) {
        int mid = L + R >> 1; 
        int val = check(mid); 
        if (val == -1) L = mid; 
        else R = min(mid, val / k + 1); 
    }
    return L; 
}