#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 - arr.size(); 
    shuffle(arr.begin(), arr.end(), Rand); 

    set<int> newarr; 
    for (int i : arr) newarr.insert(i); 

    // memset(in, 0, sizeof in); 

    for (int i : arr) {
        if (cnt == k * x) break; 
        Move_inside(i); in[i] = 1; ++cnt; newarr.erase(i); 
        if (press_button() > x) {
            Move_outside(i); in[i] = 0; --cnt; newarr.insert(i); 
            // if (cnt < k * x) {
                // for (int i : arr)
                    // if (in[i]) Move_outside(i), in[i] = 0; 
                // return cnt; 
            // }
        }
    }
    if (cnt == k * x) {
        arr.clear(); 
        for (int i : newarr) arr.emplace_back(i); 
        // for (int i : newarr) in[i] = 0; 
        return -1; 
    }
    vector<int> li = arr; 
    arr.clear(); 
    for (int i : li)
        if (newarr.find(i) != newarr.end()) Move_outside(i); 
        else arr.emplace_back(i); 
    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);  
    }
    if (k == 1) return n; 

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

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