#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
auto tryk = [&](int k){
vector<int> cur;
for(int i = 0;i < N;i++){
move_inside(i);
if(press_button() > k){
move_outside(i);
}else{
cur.push_back(i);
}
}
for(auto &i:cur) move_outside(i);
return cur.size();
};
// first check group
int gp = tryk(1);
// binary search
int bottom = 1;
int top = N;
int maxPossible = 1;
// cout << "!" << gp << endl;
while(bottom <= top){
int mid = (bottom+top)/2;
int respond = tryk(mid);
// cout << bottom << " " << top << endl;
// cout << "!" << mid << ":" << respond << endl;
if(respond == gp*mid){
maxPossible = max(maxPossible,mid);
bottom = mid+1;
}else{
top = min(respond/gp,mid-1);
}
}
// cout << bottom << " " << top << endl;
return maxPossible;
}
