#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,out;
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 = 0; i < N; ++i)
out.insert(i);
for(int i:in)
out.erase(i);
in.clear();
int low=1,high=(N/type)+1;
int bef=type;
while(high-low>1){
int mid=(high+low)/2;
int cnt=0;
for(int i:out){
move_inside(i);
in.insert(i);
if(press_button()>mid){
move_outside(i);
in.erase(i);
}
else
cnt++;
if (cnt+bef==type*mid)
break;
}
if(cnt+bef==type*mid){
low=mid;
if(high-low<=1)
break;
bef+=cnt;
for(int i:in)
out.erase(i);
in.clear();
}
else{
high=mid;
if(high-low<=1)
break;
out.clear();
for(int i:in){
move_outside(i);
out.insert(i);
}
in.clear();
}
}
return low;
}
