#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N){
vector <int> used(N, 0);
int num = 0, change = 0;
auto add = [&](int i) -> void {
if (used[i]) return;
move_inside(i);
num ++;
used[i] = 1;
change = 1;
};
auto del = [&](int i) -> void {
if (!used[i]) return;
move_outside(i);
num --;
used[i] = 0;
change = 1;
};
int last = 0;
auto qry = [&]() -> int {
if (!change) return last;
change = 0;
if (num == 1) return last = 1;
return last = press_button();
};
for (int i = 0; i < N; ++ i){
add(i);
if (qry() > 1) del(i);
}
if (num == 1) return N;
if (num == N) return 1;
int D = num;
vector <int> valid = used;
vector <int> ban(N, 0);
auto check = [&](int mid){
vector <int> g;
for (int i = 0; i < N; ++ i){
if (!used[i] && !ban[i]){
add(i);
if (qry() > mid) {
del(i);
g.push_back(i);
}
else if (last < mid && qry() == mid) g.push_back(i);
}
}
if (num == D * mid){
valid = used;
return true;
}
for (int i = 0; i < N; ++ i) if (!valid[i]) del(i);
for (int i : g) ban[i] = 1;
return false;
};
int low = 1, high = N / D;
while (low < high){
int mid = (low + high + 1) >> 1;
if (check(mid)) low = mid;
else high = mid - 1;
}
return low;
}
