#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
int min_cardinality(int n){
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> sus(n); iota(sus.begin(), sus.end(), 0); shuffle(sus.begin(), sus.end(), rng);
set<int> s;
auto in=[&](int i){
s.insert(i);
move_inside(sus[i]);
};
auto out=[&](int i){
s.erase(i);
move_outside(sus[i]);
};
for (int i=0; i<n; ++i){
in(i);
if (press_button()>1) out(i);
}
int cnt=s.size();
map<int, set<int>> memo;
memo[1]=s;
for (int i=0; i<n; ++i) memo[n].insert(i);
int l=2, r=n/cnt;
while (l<=r){
int mid=(l+r)>>1;
auto it=memo.lower_bound(mid);
set<int> t;
for (int i:it->second) if (!s.count(i)){
in(i);
if (press_button()>mid) out(i);
else t.insert(i);
}
int k=s.size();
memo[mid]=s;
if (k>=cnt*mid) l=mid+1;
else{
r=mid-1;
for (int i:t) out(i);
}
}
return r;
}
