#include "insects.h"
//#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()
namespace{
const int B=0;
const int inf=1e9;
const int mxn=2000;
vector<bool> in(mxn);
}
int min_cardinality(int n) {
vector<int> p(n);
for(int i=0;i<n;i++){
p[i]=i;
}
mt19937 rng(time(NULL));
shuffle(all(p),rng);
auto movein=[&](int x){
move_inside(p[x]);
};
auto moveout=[&](int x){
move_outside(p[x]);
};
vector<bool> in(n);
int var=0;
for(int i=0;i<n;i++){
movein(i);
in[i]=true;
if(press_button()==2){
moveout(i);
in[i]=false;
}
else{
var++;
}
}
vector<int> vec;
for(int i=0;i<n;i++){
vec.push_back(i);
}
int cnt=var;
auto check=[&](int mid){
vector<int> cur;
for(auto i:vec){
if(in[i]) continue;
movein(i);
in[i]=true;
cur.push_back(i);
cnt++;
if(press_button()>mid){
in[i]=false;
moveout(i);
cur.pop_back();
cnt--;
}
if(cnt==mid*var) break;
}
if(cnt==mid*var){
return true;
}
else{
for(auto i:cur){
if(in[i]){
moveout(i);
in[i]=false;
cnt--;
}
}
swap(cur,vec);
return false;
}
};
int l=1,r=n/var;
while(l<r){
int mid=(l+r+1)/2;
if(check(mid)){
l=mid;
}
else{
r=mid-1;
}
}
return l;
}
