#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
vector<int> ord(N);
iota(begin(ord), end(ord), 0);
mt19937 rng(1);
shuffle(begin(ord), end(ord), rng);
vector<bool> vis(N);
int inside = 0;
int diff = 0;
vector<int> took;
auto calc = [&](int till, bool first = false) -> void {
for (int i : ord) {
if (vis[i]) continue;
move_inside(i);
if (press_button() > till) {
move_outside(i);
} else {
took.push_back(i);
inside += 1;
vis[i] = 1;
if (first) diff += 1;
}
}
};
calc(1, true);
int l = 1, r = N / inside + 1;
// cout << diff << "\n";
while (l < r) {
int mid = (l + r + 1) / 2;
took.clear();
int prv = l * diff;
calc(mid);
// cerr << mid << " = " << prv << " + " << took.size() << " , total = " << diff * mid << "\n";
if (prv + (int)took.size() == diff * mid) {
l = mid;
} else {
while (took.size()) {
move_outside(took.back());
vis[took.back()] = 0;
took.pop_back();
}
r = mid - 1;
}
}
return l;
}
