#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a), end(a)
using vi = vector<int>;
int n, D;
set<int> S;
map<set<int>,int> M;
bool move_in(int i){
if(S.count(i)) return 0;
S.insert(i); move_inside(i);
return 1;
}
bool move_out(int i){
if(!S.count(i)) return 0;
S.erase(i); move_outside(i);
return 1;
}
int press(){ return press_button(); }
int min_cardinality(int N) {
n = N; D = N;
vector<int> xd(n,0); iota(all(xd),0);
random_shuffle(all(xd));
for(int i = 0; i < n; i++){
move_in(xd[i]);
if(press()>1) move_out(xd[i]), D--;
}
for(int i = 0; i < n; i++) move_out(xd[i]);
int l = 1, r = n/D;
while(l<r){
int mid = (l+r+1)/2, tot=n;
vi undo; undo.clear();
for(int i = 0; i < n; i++){
if(!move_in(xd[i])) continue;
if(press()>mid) move_out(xd[i]), tot--;
else undo.pb(xd[i]);
}
if(tot==D*mid) l = mid;
else{
for(auto u : undo) move_out(u);
r=mid-1;
}
}
return l;
}
