#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality( int n ){
vector<int> marc(n);
int k = 0;
for( int i = 0; i < n; i++ ){
move_inside(i);
if( press_button() > 1 ) move_outside(i);
else{
marc[i] = 2;
k++;
}
}
int inside = k;
auto check = [&]( int val ){
for( int i = 0; i < n; i++ ) if( marc[i] != -1 && marc[i] != 2 ){
move_inside(i);
if( press_button() > val ) move_outside(i);
else marc[i] = 1, inside++;
}
return (inside == val*k);
};
int l = 1, r = n/k;
while( l < r ){
int mid = ( l + r + 1 )/2;
if( check(mid) ){
for( int i = 0; i < n; i++ ) if( marc[i] == 1 ) marc[i] = 2;
l = mid;
}
else{
for( int i = 0; i < n; i++ ){
if( marc[i] == 1 ) move_outside(i), marc[i] = 0, inside--;
else if( marc[i] == 0 ) marc[i] = -1;
}
r = mid - 1;
}
}
return l;
}
