#include <numeric>
#include <iostream>
#include <vector>
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N) {
std::vector<int> included{};
auto x = [&](int m) -> int {
for (int i = 0; i < N; i++) {
move_inside(i);
if (press_button() > m)
move_outside(i);
else
included.push_back(i);
}
auto res = included.size();
included.clear();
return res;
};
auto k = x(1);
int l = 1;
int r = N/k + 1;
while (r - l > 1) {
auto m = (l + r) / 2;
// auto m = std::midpoint(l, r);
auto res = x(m);
// std::cout << l << ' ' << m << ' ' << r << '\n';
if (res == k * m) {
l = m;
} else {
r = m;
}
}
return l;
}
