#include "insects.h"
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int min_cardinality(int N) {
int k = 0;
stack<int> in;
queue<int> out, discard;
for (int i = 0; i < N; i++) out.push(i);
for (int i = 0; i < N; i++) {
int a = out.front();
out.pop();
move_inside(a);
if (press_button() == 1) {
++k;
in.push(a);
}
else {
move_outside(a);
out.push(a);
}
}
while (!in.empty()) {
out.push(in.top());
in.pop();
}
int l = 1, r = N / k + 1;
while (l < r - 1) {
while (!discard.empty()) {
out.push(discard.front());
discard.pop();
}
int x = (l + r) / 2;
while (!out.empty()) {
int a = out.front();
out.pop();
move_inside(a);
if (press_button() > x) {
move_outside(a);
discard.push(a);
} else in.push(a);
}
if (in.size() == k * x) {
l = x;
} else {
r = x;
while (!in.empty()) {
int a = in.top();
move_outside(a);
in.pop();
discard.push(a);
}
}
}
return l;
}
