#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int m, op=0;
bool f1(int n)
{
vector<int> hj(n, 0), ind; ind.reserve(n);
for(auto x: ind) move_outside(x); ind.clear(); fill(hj.begin(), hj.end(), 0);
for(int i=1; i<=m; i++)
{
int ad=0;
for(int j=0; j<n; j++)
{
if(!hj[j])
{
move_inside(j);int u=press_button(); if(u>i){move_outside(j);} else{hj[j]=1; ad++; ind.push_back(j);}
}
}
if(ad<op){for(auto x: ind) move_outside(x); ind.clear(); fill(hj.begin(), hj.end(), 0); return false;}
}
for(auto x:ind) move_outside(x);
return true;
}
int min_cardinality(int n) {
vector<int> f;for(int i=0; i<n; i++){move_inside(i); if(press_button()>1) move_outside(i); else {f.push_back(i); op++;}}
for(auto x:f)move_outside(x); if(op<=1) return n; if(op==n) return 1;
int l=0, r=n/op;
while(l<r)
{
m=(l+r+1)/2;if(f1(n)){l=m;} else r=m-1;
}
return l;
}
