#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int n,num;
int min_cardinality(int N) {
n = num = N;
vector<int> a;
vector<bool> mark(n,0);
for(int i = 0 ; i<n; ++i) {
move_inside(i);
if(press_button() > 1) move_outside(i),mark[i] = 1,num--;
}
if(num == 1) return n;
if(num == n) return 1;
for(int i = 0 ; i<n ;++i) if(mark[i]) a.push_back(i);
int l = 1,r = n/num;
while(l<r) {
int md = (l+r+1)/2;
int cnt = l*num;
vector<int> a1,a2;
for(int x:a) {
if(cnt == md*num) {
a2.push_back(x);
continue;
}
move_inside(x);
if(press_button() > md) move_outside(x),a2.push_back(x);
else a1.push_back(x),cnt++;
}
if(cnt == md*num) {
a = a2;
l = md;
}
else {
for(int x:a1) move_outside(x);
a = a1;
r = md-1;
}
}
return l;
}
