#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
int D = 1;
vector<int> can;
move_inside(0);
for (int i = 1; i < N; i++) {
move_inside(i);
if (press_button() == 2) {
move_outside(i);
can.push_back(i);
} else {
D++;
}
}
int l = 2, r = N / D, ans = 1;
while (l <= r) {
int m = (l + r) / 2;
vector<int> in, out;
for (int i : can) {
if ((int)in.size() == D * (m - ans)) {
out.push_back(i);
continue;
}
move_inside(i);
if (press_button() > m) {
move_outside(i);
out.push_back(i);
} else {
in.push_back(i);
}
}
if ((int)in.size() == D * (m - ans)) {
l = m + 1;
ans = m;
can = out;
} else {
r = m - 1;
can = in;
for (auto x : can) {
move_outside(x);
}
}
}
return ans;
}
