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