#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
int min_cardinality(int n) {
vector<int> v(n);
iota(all(v), 0);
int k = 0;
vector<int> er;
for(int i = 0; i < n; i++){
move_inside(i);
if(press_button() == 1){
k++;
er.pb(i);
}else move_outside(i);
}
for(auto i:er)move_outside(i);
int l = 1, r = n/k+1, ans = 1;
while(l <= r){
int m = (l+r)>>1;
//~ cout << m << '\n';
int d = 0;
vector<int> er;
for(int i:v){
move_inside(i);
if(press_button() <= m){
d++;
er.pb(i);
}else move_outside(i);
}
//~ for(auto i:er)cout << i << ' ';
//~ cout << '\n';
if(k*m == d){
ans = m;
l = m+1;
}else{
r = m-1;
}
for(auto i:er)move_outside(i);
}
return ans;
}
