#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int n) {
set<int> machine;
int distinct = 0;
for (int i = 0; i < n; i++) {
move_inside(i);
machine.insert(i);
distinct++;
if (press_button() == 2) {
move_outside(i);
machine.erase(i);
distinct--;
}
}
auto empty_machine = [&]() {
for (int i : machine) {
move_outside(i);
}
machine.clear();
};
empty_machine();
auto Check = [&](int d) {
// the minimum >= d
for (int i = 0; i < n; i++) {
if (d * distinct == machine.size()) {
empty_machine();
return true;
}
move_inside(i);
machine.insert(i);
if (press_button() == d + 1) {
move_outside(i);
machine.erase(i);
}
}
int sz = machine.size();
empty_machine();
return (d * distinct == sz);
};
int low = 1, high = n, idx = -1;
while (low <= high) {
int mid = (low + high) >> 1;
if (Check(mid)) {
idx = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return idx;
}
