#include<bits/stdc++.h>
#include "insects.h"
using namespace std;
deque<int> box;
set<int> sure , unsure , notun;
int chek;
int min_cardinality(int N) {
int comp = 0;
sure.clear();
unsure.clear();
notun.clear();
for( int z = 0; z < N; z++ ) {
move_inside(z);
chek = press_button();
if( chek == 2 ) {
move_outside(z);
unsure.insert(z);
}
else{
comp++;
sure.insert(z);
}
}
if( comp == 1 ) return N;
else{
int boro = ( N - (N % comp ) ) / comp;
int l = 1;
int r = boro;
while( l != r ) {
int m = ( l + r + 1 ) / 2;
for( auto it = unsure.begin() ; it != unsure.end(); ++it ) {
int z = *it;
move_inside(z);
chek = press_button();
if( chek > m ) {
move_outside(z);
}
else{
notun.insert(z);
}
}
if( ( (int)notun.size() + (int)sure.size() ) == (m * comp) ) {
l = m;
for( auto it = notun.begin() ; it != notun.end(); ++it ) {
int z = *it;
sure.insert(z);
unsure.erase(z);
}
notun.clear();
}
else{
r = m - 1;
unsure.clear();
for( auto it = notun.begin(); it != notun.end(); ++it ) {
move_outside(*it);
unsure.insert(*it);
}
notun.clear();
}
}
return r;
}
}
