#include "insects.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define vi vector<int>
#define vb vector<bool>
#define pb push_back
using namespace std;
int min_cardinality(int N) {
vi perm;
f0r(i, N)perm.pb(i);
random_shuffle(perm.begin(), perm.end());
vb in(N);
vb notin(N);
int cnt = 0;
f0r(i, N){
move_inside(perm[i]);
cnt++;
in[i] = 1;
int x = press_button();
if(x > 1){
move_outside(perm[i]);
cnt--;
in[i] = 0;
}
}
int d = 0;
f0r(i, N){
if(in[i])d++;
}
if(d == 1)return N;
int lo = 1;
int hi = N/d+1;
while(lo < hi){
int mid = lo + (hi - lo + 1) / 2;
vi lst;
vi lst2;
f0r(i, N){
if(!in[i] && !notin[i]){
move_inside(perm[i]);
cnt++;
in[i] = 1;
int x = press_button();
if(x > mid){
move_outside(perm[i]);
cnt--;
in[i] = 0;
}
else{
lst.pb(perm[i]);
lst2.pb(i);
}
}
if(cnt == d * mid){
break;
}
}
int cnt2 = 0;
f0r(i, N){
if(in[i])cnt2++;
}
if(cnt2 == d * mid){
lo = mid;
}
else{
hi = mid - 1;
f0r(i, N){
if(!in[i]){
notin[i] = 1;
}
}
f0r(i, lst.size()){
move_outside(lst[i]);
cnt--;
in[lst2[i]]= 0;
}
}
}
return lo;
}
