#include "insects.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
constexpr ll mod = 1'000'002'022;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define ln "\n"
int min_cardinality(int N) {
vi distinct;
rep(i,0,N){
move_inside(i);
if(press_button() == 1) distinct.pb(i);
else move_outside(i);
}
for(auto el: distinct) move_outside(el);
std::set<ll> inside, outside;
rep(i,0,N) outside.insert(i);
ll left = 0, right = N/distinct.size()+1;
while(left+1 < right){
ll mid = (left+right)/2;
{
vi rm;
for(auto el: outside){
move_inside(el);
if(press_button() > mid) move_outside(el);
else{
inside.insert(el);
rm.pb(el);
}
}
for(auto el: rm) outside.erase(el);
if(mid*distinct.size() == inside.size()){
inside.clear();
left = mid;
}
else{
right = mid;
outside.clear();
for(auto el: inside) move_outside(el);
std::swap(outside, inside);
}
}
}
return left;
}
