#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
int D = 1;
vector<int> inside(N), outside(N), leader(N);
move_inside(0); inside[0] = leader[0] = 1;
for (int i = 1; i < N; i++) {
move_inside(i);
if (press_button() == 2) {
move_outside(i);
outside[i] = 1;
} else {
D++;
inside[i] = leader[i] = 1;
}
}
int l = 1, r = N / D, cur = D;
while (l < r) {
int m = (l + r + 1) / 2;
vector<int> last;
for (int i = 0; i < N; i++) {
if (inside[i]) continue;
move_inside(i);
if (press_button() > m) {
move_outside(i);
} else {
last.push_back(i);
inside[i] = 1;
outside[i] = 0;
cur++;
}
}
if (cur >= D * m) {
l = m;
} else {
if (l == r) break;
r = m - 1;
for (auto x : last) {
move_outside(x);
inside[x] = 0;
outside[x] = 1;
cur--;
}
}
}
return l;
}
