#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int n) {
int dst = 0;
{
set<int> hier;
for (int i = 0; i < n; i++)
{
move_inside(i);
int val = press_button();
if(val>1)
move_outside(i);
else
dst++,hier.insert(i);
}
for(int x: hier)
move_outside(x);
}
function<bool(int)> check = [&](int x)
{
if(x>n)return true;
if(x==0)return false;
int sz = 0;
set<int> hier;
for(int i = 0; i< n; i++)
{
move_inside(i);
int val = press_button();
if(val>x)
move_outside(i);
else
sz++,hier.insert(i);
}
for(int y: hier)
move_outside(y);
return sz < x*dst;
};
int l = 0,r = n+1;
while(r-l)
{
int mid = l+r+1>>1;
if(check(mid))
r = mid-1;
else
l = mid;
}
return l;
}
