#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],prv[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,mt19937(998244353));
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;
copy(in,in+N,prv);
while (l!=r){
int k=1+(l+r)/2;
int remaining=0;
vector<int> rej;
for (int i=0;i<N;i++) if (!out[i]&&!in[i]) remaining++;
for (int i=0;i<N;i++) if (!out[i]&&!in[i]){
if (cnt+remaining<K*k) break;
if (K*k==cnt) break;
remaining--;
ins(i);
if (press_button()>k) rem(i),rej.push_back(i);
}
cur=k;
if (K*k==cnt){
copy(in,in+N,prv);
l=k;
}else{
for (auto i:rej) out[i]=1;
for (int i=0;i<N;i++) if (in[i]&&!prv[i]) rem(i);
r=k-1;
}
}
return l;
}
