#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int baseval;
set <int> rem;
int init(int n){
vector <int> v;
v.push_back(0);
move_inside(0);
for (int i=1; i<n; i++){
move_inside(i);
if (press_button()==1) v.push_back(i);
else move_outside(i);
}
baseval=1;
for (int i=0; i<n; i++) rem.insert(i);
for (int i:v) rem.erase(i);
return v.size();
}
int min_cardinality(int N){
int m=init(N);
int l=1,r=N/m;
while (l<r){
int mid=(l+r+1)/2;
vector <int> in,out;
bool done=0;
for (int i:rem){
move_inside(i);
if (press_button()>mid){
out.push_back(i);
move_outside(i);
continue;
}
in.push_back(i);
if (baseval*m+in.size()==mid*m){
baseval=mid;
for (int j:in) rem.erase(j);
done=1;
break;
}
}
if (done) l=mid;
else {
r=mid-1;
for (int i:out) rem.erase(i);
for (int i:in) move_outside(i);
}
}
return l;
}
