#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int getnum(int N, int M){
set<int> in;
int lr = 0;
for (int i = 0 ; i < N ; ++i){
move_inside(i);
lr = press_button();
//cout<<lr<<" "<<M<<endl;
if (lr>M)move_outside(i);
else in.insert(i);
}
for (auto it : in)move_outside(it);
if (lr < M)return -1;
return in.size();
}
int min_cardinality(int N) {
int groups = getnum(N, 1);
int l = 0;
int r = N/groups + 1;
while (l + 1 < r){
int m = (l + r) /2;
int rta = getnum(N,m);
//cout<<m<<" | "<<rta<<endl;
if (rta==groups*m)l = m;
else r = m;
}
if (getnum(N,l)==l*groups)return l;
else return l+1;
}
