#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int min_cardinality(int n) {
int l=2, r=n, ans=n;
int in = 0;
vector<bool> vis(n);
vector<int> v;
for(int i=0; i<n; i++) {
move_inside(i);
vis[i] = 1;
in++;
if(press_button() == 2) {
move_outside(i);
vis[i] = 0;
in--;
} else {
v.push_back(i);
}
}
int diff = v.size();
if(diff == 1) return n;
if(diff == n) return 1;
r = n / diff;
while(l <= r) {
int mid = (l + r) / 2;
vector<int> now;
for(int i=0; i<n; i++) {
if(vis[i] || in == mid * diff) continue;
move_inside(i);
if(press_button() == mid + 1) {
move_outside(i);
} else in++, vis[i] = 1, now.push_back(i);
}
if(in == mid * diff) {
ans = mid, l = mid + 1;
}
else {
r = mid - 1;
for(int u : now) {
move_outside(u);
vis[u] = 0;
in--;
}
}
}
return ans;
}
