#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=2e3+5;
mt19937 rng(time(0));
int p[nx], cnt, sz, in[nx], t[nx], s[nx];
vector<pair<int, int>> v;
int min_cardinality(int N) {
cin.tie(NULL)->sync_with_stdio(false);
for (int i=0; i<N; i++) v.push_back({rng(), i});
sort(v.begin(), v.end());
for (int i=0; i<N; i++) p[v[i].second]=i;
for (int i=0; i<N; i++)
{
move_inside(p[i]);
if (press_button()==1) cnt++, in[i]=1, s[i]=1;
else move_outside(p[i]);
}
if (cnt==1) return N;
if (cnt==N) return 1;
int l=1, r=N/cnt;
sz=cnt;
while (l<r)
{
int md=(l+r+1)/2;
for (int i=0; i<N; i++)
{
if (s[i]||t[i]) continue;
move_inside(p[i]);
if (press_button()>md) move_outside(p[i]);
else sz++, in[i]=1;
}
if (sz==cnt*md)
{
l=md;
for (int i=0; i<N; i++) if (in[i]) s[i]=1;
}
else
{
r=md-1;
for (int i=0; i<N; i++) if (!in[i]) t[i]=1;
for (int i=0; i<N; i++) if (in[i]&&!s[i]) in[i]=0, move_outside(p[i]), sz--;
}
}
return l;
}
