#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
bool skip[MAXN];
int solve(int l, int r, vector<int> &reps, vector<int> &ex) { // also move all outside
if (ex.size() < reps.size()) return 1;
if (l == r) {
move_outside(reps[l]);
return ex.size()+1;
}
int mid = (l+r)/2;
for (int i = mid+1; i <= r; i++) move_outside(reps[i]);
vector<int> lex, rex;
for (int v: ex) {
move_inside(v);
if (press_button() > 1) {
lex.push_back(v);
}
else rex.push_back(v);
move_outside(v);
}
int a = solve(l, mid, reps, lex);
if (a == 1) return 1;
for (int i = mid+1; i <= r; i++) move_inside(reps[i]);
return min(a, solve(mid+1, r, reps, rex));
}
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)]);
vector<int> reps;
vector<int> extra;
for (int i = 0; i < n; i++) {
move_inside(perm[i]);
if (press_button() > 1) {
move_outside(perm[i]);
extra.push_back(perm[i]);
}
else {
skip[i] = 1;
reps.push_back(perm[i]);
}
}
return solve(0, reps.size()-1, reps, extra);
}
