#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
const int NN = 1e5 + 10;
bool in[NN];
mt19937 rng(10184104810471);
int rnd(int l, int r) {
return l + rng() % (r - l + 1);
}
int min_cardinality(int n) {
int type = 0;
vector<int> candidate;
for(int i = 0; i < n; i++) {
move_inside(i);
if (press_button() == 1) {
++type;
in[i] = 1;
}
else {
move_outside(i);
candidate.push_back(i);
}
}
int l = 2, r = n / type, ans = 1;
int cur = 1;
while (l <= r) {
shuffle(candidate.begin(), candidate.end(), rng);
int mid = type <= 75 ? (l + r + 1) / 2 : (l + r) / 2;
assert(cur <= mid);
int last = cur;
for(auto &i : candidate) {
move_inside(i);
int nxt = press_button();
if (nxt > mid) {
move_outside(i);
in[i] = 0;
}
else {
cur = nxt;
in[i] = 1;
}
}
int total = 0;
for(int i = 0; i < n; i++) total += in[i];
vector<int> _candidate;
if (cur == mid && mid * type == total) {
for(auto &i : candidate) if (!in[i]) _candidate.push_back(i);
l = mid + 1;
ans = mid;
}
else {
for(auto &i : candidate) if (in[i]) {
_candidate.push_back(i);
move_outside(i);
in[i] = 0;
}
r = mid - 1;
cur = last;
}
candidate = _candidate;
}
return ans;
}
