#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
int min_cardinality(int N) {
int d = 0;
bool marked[N]; memset(marked,false,sizeof(marked));
vector<int> to_remove;
for(int i=0;i<N;i++) {
move_inside(i);
int res = press_button();
if(res>1) {
move_outside(i);
}
else {
d++;
marked[i]=true;
to_remove.push_back(i);
}
}
for(int x: to_remove) move_outside(x);
int ans = 0;
int lo=1,hi=N/d;
set<int> s;
while(lo<=hi) {
int mid = (lo+hi)/2;
to_remove.clear();
int cnt=0;
for(int i=0;i<N;i++) {
if(s.find(i)==s.end()) move_inside(i);
s.insert(i);
int res = press_button();
if(res > mid) {
move_outside(i);
s.erase(i);
}
else {
cnt++;
to_remove.push_back(i);
}
}
if(cnt==d*mid) {
lo=mid+1;
ans=max(ans,mid);
}
else {
hi=mid-1;
for(int x: to_remove) {
move_outside(x);
s.erase(x);
}
}
}
return ans;
}
