#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
int min_cardinality(int N){
vector<bool> in(N, false);
int t = 0;
for (int i=0; i<N; i++){
move_inside(i);
in[i] = true;
t++;
if (press_button() > 1){
move_outside(i);
in[i] = false;
t--;
}
}
if (t == 1) return N;
int k = t;
int l = 1, r = N/t+1;
bool b = false;
while (l < r-1){
int m = (l+r)/2;
if (b){
for (int i=0; i<N; i++){
if (!in[i]) continue;
move_outside(i);
in[i] = false;
k--;
}
}
int k2 = 0;
for (int i=0; i<N; i++){
if (k2+N-i < t*m) break;
if (in[i]){
k2++;
continue;
}
move_inside(i);
in[i] = true;
k++;
k2++;
if (press_button() > m){
move_outside(i);
in[i] = false;
k--;
k2--;
}
}
if (k == t*m){
l = m;
b = false;
}
else {
r = m;
b = true;
}
}
return l;
}
