#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
int min_cardinality(int N) {
int cnt = 0, add = 0;
unordered_set<int> unique;
for (int i = 0; i < N; i++) {
cnt++;
move_inside(i);
unique.insert(i);
int res = press_button();
if (res == 2) {
cnt--;
move_outside(i);
unique.extract(i);
}
}
auto check = [&](int m) -> bool {
unordered_set<int> ts;
int curr = cnt + add;
for (int i = 0; i < N; i++) {
if (unique.count(i)) continue;
curr++;
move_inside(i);
ts.insert(i);
int res = press_button();
if (res > m) {
curr--;
move_outside(i);
ts.extract(i);
}
}
if (curr >= cnt * m) {
for (auto &x : ts) unique.insert(x);
add += ts.size();
} else {
for (auto &x : ts) move_outside(x);
}
return curr < cnt * m;
};
int l = 0, r = N / cnt;
while (r - l > 1) {
int m = (l + r) / 2;
if (check(m)) {
r = m;
} else {
l = m;
}
}
if (check(r)) r = l;
return r;
}
