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

// 最多问 3n 次询问
int n, m, k, id[N]; 
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
    int cnt = n; 
    for (int i = 1; i <= n; ++i) {
        Move_inside(i); in[i] = 1; 
        if (press_button() > x) {
            Move_outside(i), in[i] = 0, --cnt; 
            if (cnt < k * x) {
                for (int i = 1; i <= n; ++i)
                    if (in[i]) Move_outside(i), in[i] = 0; 
                return 0; 
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        if (in[i]) Move_outside(i); 
    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), in[i] = 1; 
        if (press_button() > 1) Move_outside(i), in[i] = 0, --k; 
    }
    for (int i = 1; i <= n; ++i)
        if (in[i]) Move_outside(i); 
    if (k == 1) return 1; 
    int L = 1, R = n / k + 1; 
    while (L + 1 != R) {
        int mid = L + R >> 1; 
        if (check(mid)) L = mid; 
        else R = mid; 
    }
    return L; 
}

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

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

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