#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> p;
int cnt;
int pressButton() {
return press_button();
}
void moveInside(int i) {
move_inside(p[i]);
}
void moveOutside(int i) {
move_outside(p[i]);
}
int minCardinality(int N) {
vector<int> candidates(N);
iota(candidates.begin(), candidates.end(), 0);
while (1) {
int MAX = int(candidates.size()) / cnt;
if (candidates.size() == MAX) return MAX;
vector<int> inside;
for (int i : candidates) {
moveInside(i);
if (pressButton() > MAX) moveOutside(i);
else inside.emplace_back(i);
}
if (int(inside.size()) == cnt * MAX) return MAX;
assert(int(inside.size()) < cnt * MAX);
assert(int(inside.size() < int(candidates.size())));
for (int i : inside) moveOutside(i);
candidates = inside;
}
}
int min_cardinality(int N) {
p.assign(N, 0);
iota(p.begin(), p.end(), 0);
shuffle(p.begin(), p.end(), rng);
vector<int> e;
for (int i = 0; i < N; i++) {
moveInside(i);
e.emplace_back(i);
if (pressButton() > 1) moveOutside(i);
else ++cnt;
}
for (int i : e) moveOutside(i);
if (cnt == 1) return N;
if (cnt == N) return 1;
return minCardinality(N);
}
