#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
mt19937 rng(time(0));
int min_cardinality(int n) {
vector<int>vals;
for(int i=0;i<n;i++){
vals.pb(i);move_inside(i);
if(press_button()==2) vals.pop_back(),move_outside(i);
}
int S=vals.size();
if(S==1) return n;
bool skip[n+10]={false},ubacen[n+10]={false};
int l=1,r=n/S+1,res=1;
while(l+1<r){
int mid=l+r>>1,ct=0;
for(int i=0;i<n;i++) if(ubacen[i]) ct++;
vector<int>a,b,ind;
for(int i=0;i<n;i++) if(!skip[i]&&!ubacen[i]) ind.pb(i);
shuffle(ind.begin(),ind.end(),rng);
for(auto i:ind){
if(ubacen[i]||skip[i]) continue;
a.pb(i);move_inside(i);
if(press_button()>mid) a.pop_back(),b.pb(i),move_outside(i);
if(a.size()+ct==mid*S) break;
}
if(a.size()+ct==mid*S){
res=mid;l=mid;
for(auto i:a) ubacen[i]=true;
}
else{
for(auto i:a) move_outside(i);
for(auto i:b) skip[i]=true;
r=mid;
ct=0;for(int i=0;i<n;i++) if(!skip[i]) ct++;
r=min(r,ct/S+1);
}
}
return l;
}
