#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int n) {
vector<int> ind; set<int> rm; ind.reserve(n);
int lk=0, pl=-1; move_inside(0); ind.push_back(0);
for(int i=1; i<n; i++)
{
move_inside(i);
if(press_button()>1){move_outside(i); rm.insert(i);} else ind.push_back(i);
}
int k=ind.size(); if(k==0) return 0;
int l=1, r=n/k;
while (l<r)
{
r = min(r, l + (int)(rm.size() / k));
int m=(l+r+1)/2; long long ne=1LL*k*(m-l); if(ne>rm.size()){r=m-1; continue;}
vector<int> y, h; y.reserve((size_t)min<long long>(ne, rm.size())); h.reserve(rm.size()); long long pu=0;
for(auto it =rm.begin();it != rm.end() && y.size() < ne; it++, pu++)
{
long long u=rm.size()-pu, v=ne-y.size(); if(u<v) break; int x=*it; move_inside(x); if(press_button()>m){move_outside(x); h.push_back(x);}
else y.push_back(x);
}
if(y.size()==ne)
{
for(auto x:y) rm.erase(x); l=m;
}
else
{
if(!y.empty()){for(auto x:y)move_outside(x);}
for(auto x:h) rm.erase(x); r=m-1;
}
}
return l;
}
