#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 1e6 + 10;
int n;
bool flag[MAXN];
int min_cardinality(int n_) {
n = n_;
vector<int> vec;
for (int i = 0; i < n; i++)
vec.push_back(i);
int base_size = MAXN;
shuffle(all(vec), rng);
for (int i = 1; i <= n + 1; i++) {
int tsize = 0;
int ind = 0;
for (int e : vec) {
if (!flag[e]) {
move_inside(e);
if (press_button() == i) tsize++, flag[e] = true;
else move_outside(e);
if (tsize == base_size) {
rotate(vec.begin(), vec.begin() + ind, vec.end());
break;
}
ind++;
}
}
if (tsize < base_size) {
if (base_size == MAXN) base_size = tsize;
else return i - 1;
}
}
return 0;
}
