#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int min_cardinality(int N) {
n = N;
vector<int> v;
set<int> in, out;
for(int i=0; i<n; i++){
move_inside(i);
v.push_back(i);
if(press_button()>=2){
move_outside(i);
v.pop_back();
out.insert(i);
}
}
mt19937 mt(4732012);
int lb = 0, rb = n / v.size();
while(lb<rb){
int mb = (lb+rb+1)/2;
vector<int> order(out.begin(), out.end());
shuffle(order.begin(), order.end(), mt);
for(auto x:order){
if(v.size()*mb==in.size())
break;
out.extract(x);
in.insert(x);
move_inside(x);
if(press_button()>mb+1){
move_outside(x);
in.extract(x);
out.insert(x);
}
}
if(v.size()*mb==in.size()){
lb=mb;
}else{
rb=mb-1;
for(auto x:in){
move_outside(x);
out.insert(x);
}
in.clear();
}
}
return lb+1;
}
