#include "insects.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
using namespace std;
const int MAX=2005;
bool in[MAX],out[MAX];
int idx[MAX];
int cnt=0;
void ins(int i){
move_inside(idx[i]);
in[i]=1;
cnt++;
}
void rem(int i){
move_outside(idx[i]);
in[i]=0;
cnt--;
}
int min_cardinality(int N) {
for (int i=0;i<N;i++) idx[i]=i;
shuffle(idx,idx+N,random_device());
int K=0; // Unique
for (int i=0;i<N;i++){
ins(i);
if (press_button()>1) rem(i);
else K++;
}
int l=1,r=N/K;
int cur=1;
while (l!=r){
int k=1+(l+r)/2;
if (k>cur){
for (int i=0;i<N;i++) if (!out[i]&&!in[i]){
ins(i);
if (press_button()>k) rem(i);
}
}else{
for (int i=0;i<N;i++) if (!in[i]) out[i]=1;
for (int i=0;i<N;i++) if (in[i]) rem(i);
for (int i=0;i<N;i++) if (!out[i]){
ins(i);
if (press_button()>k) rem(i);
}
}
cur=k;
if (K*k==cnt){
l=k;
}else{
r=k-1;
}
}
return l;
}
