#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];
bool ban[maxn];
int lst;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
assert(l <= r);
return uniform_int_distribution<int> (l, r)(rng);
}
int min_cardinality(int N) {
n = N;
int ds = 0;
vector<int> p(n);
iota(p.begin(), p.end(), 0);
shuffle(p.begin(), p.end(), rng);
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 = 2, r = n / ds;
int res = 1;
int cnt = 0;
while (l <= r) {
int mid = (l + r) >> 1;
vector<int> niu, bb;
for (int oi = 0; oi < n; ++oi) {
int i = p[oi];
if (vis[i] || ban[i]) continue;
move_inside(i);
if (press_button() > mid) {
move_outside(i);
bb.push_back(i);
} else {
niu.push_back(i);
++cnt;
vis[i] = 1;
}
if (cnt == 1ll * mid * ds) break;
}
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;
}
for (auto i : bb) {
ban[i] = 1;
}
}
}
return res;
}
