#include "insects.h"
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int inside = 0;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int min_cardinality(int n) {
int uniq = 0;
for (int i = 0; i < n; ++i) {
move_inside(i);
if (press_button() > 1) {
move_outside(i);
v.push_back(i);
} else uniq++;
}
if (uniq == 1) return n;
if (uniq > n / 2) return 1;
inside = uniq;
int left = 1;
int right = n / uniq;
while (left < right) {
int mid = (left + right + 1) / 2;
vector<int> in;
int mx = mid;
int gc = 0;
shuffle(v.begin(), v.end(), rng);
for (int x : v) {
move_inside(x);
if (press_button() > mx) {
move_outside(x);
} else {
in.push_back(x);
gc++;
}
if ((inside + gc) / mx == uniq) break;
}
if ((inside + gc) / mx == uniq) {
inside += gc;
for (int x : in) v.erase(find(v.begin(), v.end(), x));
left = mid;
} else {
v = in;
right = mid - 1;
for (int x : in) move_outside(x);
}
//cout << v.size() << endl;
}
return left;
}
