#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int op=0, c=0, pk=0;
int min_cardinality(int n) {
vector<int> ind, rm; ind.reserve(n); rm.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.push_back(i);} else ind.push_back(i);
}
int k=ind.size(); if(k==0) return 0;
int l=1, r=n/k;
while (l<r)
{
int m=(l+r+1)/2; long long ne=1LL*k*(m-l); vector<int> y, h; y.reserve((size_t)min<long long>(ne, rm.size())); h.reserve(rm.size());
if(ne>(long long)rm.size()){r=m-1; continue;}
for(int x: rm)
{
if(y.size()==ne) break; move_inside(x); if(press_button()>m){move_outside(x); h.push_back(x);}
else{y.push_back(x);}
}
if(y.size()==ne)
{
vector<char> mx(n, 0); for(auto x:y) mx[x]=1; vector<int>np; np.reserve(rm.size()-y.size());
for(auto x:rm) if(!mx[x]) np.push_back(x); rm.swap(np); l=m;
}
else
{
for(auto x: y) move_outside(x); vector<char>mx(n, 0); for(auto x: h)mx[x]=1; vector<int>np; np.reserve(rm.size()-h.size());
for(auto x:rm) if(!mx[x]) np.push_back(x); rm.swap(np); r=m-1;
}
}
return l;
}
