#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);
if(gp <= 8){
int ans = N;
vector<int> vis(N,false);
for(int t = 0;t < gp;t++){
vector<int> cur;
for(int i = 0;i < N;i++){
if(vis[i]) continue;
move_inside(i);
if(press_button() > cur.size()){
cur.push_back(i);
}else{
move_outside(i);
}
}
for(auto &i:cur) vis[i] = true;
for(auto &i:cur) move_outside(i);
ans = min(ans,(int)cur.size());
}
return ans;
}
// binary search
int bottom = 1;
int top = N/gp;
int maxPossible = 1;
while(bottom <= top){
int mid = (bottom+top)/2;
int respond = tryk(mid);
if(respond == gp*mid){
maxPossible = max(maxPossible,mid);
bottom = mid+1;
}else{
top = min(respond/gp,mid-1);
}
}
return maxPossible;
}
