#include "insects.h"
#include <set>
#include <iostream>
namespace ruhan {
using namespace std;
int N;
set<int> insects;
set<int> machine, new_added;
int last_pb = -1;
void work (int k) {
new_added.clear();
for (int i : insects) {
if (machine.count(i)) continue;
move_inside(i);
last_pb = press_button();
if (last_pb <= k) {
machine.insert(i);
new_added.insert(i);
} else {
move_outside(i);
}
}
}
void undo () {
for (int i : new_added) {
move_outside(i);
machine.erase(i);
}
new_added.clear();
}
int min_cardinality (int N_) {
N = N_;
machine.clear();
new_added.clear();
last_pb = -1;
insects.clear();
for (int i = 0; i < N; i++) {
insects.insert(i);
}
work(1);
const int T = machine.size();
if (T == 1) return N;
if (last_pb == 1) return 1;
int x = 1;
while (x <= N) x <<= 1;
x >>= 1;
int k = 1;
for (; x > 0; x >>= 1) {
if ((k + x) * T > N) continue;
work (k + x);
if ((int)machine.size() == (k + x) * T) {
k += x;
} else {
insects = machine;
undo();
}
}
return k;
}
};
int min_cardinality(int N) {
return ruhan::min_cardinality(N);
}
