#include<bits/stdc++.h>
#include "insects.h"
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int min_cardinality(int n){
set<int>d, s;
vector<int>perm(n);
iota(perm.begin(), perm.end(), 0);
shuffle(perm.begin(), perm.end(), rng);
for(int& i : perm){
move_inside(i);
if(press_button() == 2){
move_outside(i);
s.insert(i);
}
else{
d.insert(i);
}
}
int cnt_d = d.size(), low = 2, high = n / cnt_d, ans = 1;
while(low <= high){
int mid = (low + high) >> 1;
vector<int>S(s.begin(), s.end()), add, sub;
shuffle(S.begin(), S.end(), rng);
for(int& i : S){
if(d.size() == mid * cnt_d){
break;
}
move_inside(i);
if(press_button() > mid){
move_outside(i);
sub.emplace_back(i);
}
else{
add.emplace_back(i);
d.insert(i);
}
}
if(d.size() == mid * cnt_d){
for(int& x : add){
s.erase(x);
}
low = (ans = mid) + 1;
}
else{
for(int& x : add){
d.erase(x);
move_outside(x);
}
for(int& x : sub){
s.erase(x);
}
high = mid - 1;
}
}
return ans;
}
