#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int) s.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(131415889);
int min_cardinality(int n) {
vector<pair<int, vector<int>>> s;
vector<int> p(n);
for (int i = 0; i < n; i++) p[i] = i;
shuffle(all(p), rng);
s.push_back({1, {0}});
move_inside(0);
for (int i = 1; i < n; i++) {
move_inside(i);
if (press_button() > 1) {
bool ok = 0;
sort(rall(s));
for (int j = 0; j < sz(s); j++) {
if (s[j].f >= n / sz(s)) continue;
move_outside(s[j].s.back());
if (press_button() == 1) {
s[j].s.push_back(i);
s[j].f++;
ok = 1;
break;
}
move_inside(s[j].s.back());
}
if (!ok) move_outside(i);
continue;
}
s.push_back({1, {i}});
}
sort(all(s));
return s[0].f;
}
