#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N){
int type=0;
set<int> in;
for(int i=0;i<N;i++){
move_inside(i);
in.insert(i);
if(press_button()>1){
move_outside(i);
in.erase(i);
}
else
type++;
}
for(int i:in)
move_outside(i);
in.clear();
int low=1,high=N+1;
while(high-low>1){
int mid=(high+low)/2;
int cnt=0;
for(int i=0;i<N;i++){
move_inside(i);
in.insert(i);
if(press_button()>mid){
move_outside(i);
in.erase(i);
}
else
cnt++;
}
for(int i:in)
move_outside(i);
in.clear();
if(cnt==type*mid)
low=mid;
else
high=mid;
}
return low;
}
