#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int m, op=0, c=0, pk=0; vector<bool> fg; vector<int> uh;
bool f1(int n)
{
if(uh.empty()) return (c==op*m);
vector<int> ind; vector<bool> ag(fg.size()); int i=pk, lk=0, s=uh.size();
while(lk<s&&c<op*m)
{
move_inside(uh[i]);
if(press_button()>m){move_outside(uh[i]);}else {fg[uh[i]]=true; c++; ind.push_back(uh[i]); ag[uh[i]]=true;}
i++; if(i==s) i=0; lk++;
if(op*m-c>0&&s-lk<op*m-c) break;
}
if(c==op*m)
{
if(!ind.empty()){uh.erase(remove_if(uh.begin(), uh.end(), [&](int x){ return ag[x]; }), uh.end());}
if(uh.empty()) pk=0; else pk=i%uh.size(); return true;
}
for(auto x:ind){move_outside(x); fg[x]=false; c--;}
if(uh.empty()) pk=0; else pk=i%uh.size();
return false;
}
int min_cardinality(int n) {
op=0; c=0; pk=0; fg.assign(n, false); for(int i=0; i<n; i++){move_inside(i); if(press_button()>1) move_outside(i); else {fg[i]=true; c++; op++;}}
for(int i=0; i<n; i++) {if(!fg[i]) uh.push_back(i);} if(op<=1) return n; if(op==n) return 1;
int r = n / op, l = 1,st = 1;
while (l + st <= r) st <<= 1; st >>= 1;
while (st > 0) {
m = l + st;
if (f1(n)) l = m;
st >>= 1;
}
return l;
}
