#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
bool skip[MAXN];
int min_cardinality(int n) {
vector<int> perm(n);
iota(perm.begin(), perm.end(), 0);
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
for (int i = 1; i < n; i++) swap(perm[i], perm[gen()%(i+1)]);
int mn = n;
int num_found = 0;
while (num_found < n) {
// cerr << num_found << "\n";
int num = 0;
vector<int> inside;
for (int i = 0; i < n; i++) {
if (skip[i]) continue;
move_inside(i);
if (press_button() != num+1) move_outside(i);
else {
num++;
inside.push_back(i);
}
}
if (num == 1) return 1;
num_found += num;
for (int v: inside) {
skip[v] = 1;
move_outside(v);
}
mn = min(mn, num);
}
return mn;
}
