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