#include "bits/stdc++.h"
#include "insects.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
namespace {
const int maxn = 2005;
int n;
bool vis[maxn];
int lst;
}
int min_cardinality(int N) {
n = N;
int res = 0;
int ds = 0;
vector<int> xx;
for (int i = 0; i < n; ++i) {
move_inside(i);
if (press_button() > 1) move_outside(i);
else {
++ds;
xx.push_back(i);
}
}
while (!xx.empty()) {
move_outside(xx.back());
xx.pop_back();
}
debug(ds);
int l = 1, r = n / ds;
int cnt = 0;
while (l <= r) {
int mid = (l + r) >> 1;
vector<int> niu;
for (int i = 0; i < n; ++i) {
if (vis[i]) continue;
move_inside(i);
if (press_button() > mid) {
move_outside(i);
} else {
niu.push_back(i);
++cnt;
vis[i] = 1;
}
}
if (cnt == 1ll * mid * ds) {
res = mid;
l = mid + 1;
} else {
r = mid - 1;
for (auto i : niu) {
vis[i] = 0;
move_outside(i);
--cnt;
}
}
}
return res;
}
