#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;
while (l <= r) {
int mid = (l + r) >> 1;
if (lst < mid) {
for (int i = 0; i < n; ++i) {
if (vis[i]) continue;
move_inside(i);
if (press_button() > mid) {
move_outside(i);
} else {
xx.push_back(i);
vis[i] = 1;
}
}
} else {
while (!xx.empty()) {
move_outside(xx.back());
vis[xx.back()] = 0;
xx.pop_back();
}
for (int i = 0; i < n; ++i) {
move_inside(i);
if (press_button() > mid) {
move_outside(i);
} else {
xx.push_back(i);
vis[i] = 1;
}
}
}
if ((int)xx.size() == 1ll * mid * ds) {
res = mid;
l = mid + 1;
} else r = mid - 1;
lst = mid;
}
return res;
}
