#include <algorithm>
#include <numeric>
#include <iostream>
#include <set>
#include <vector>
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N) {
std::set<int> included{};
std::vector<int> used{};
for (int i = 0; i < N; i++)
used.push_back(i);
auto eval = [&](int m) -> int {
for (int x : used) {
if (included.contains(x))
continue;
move_inside(x);
if (press_button() > m)
move_outside(x);
else
included.insert(x);
}
return included.size();
};
auto k = eval(1);
for (auto x : included)
move_outside(x);
included.clear();
int l = 1;
int r = N/k + 1;
bool filled = false;
while (r - l > 1) {
auto m = l + (r - l) / 3;
// auto m = (l + r) / 2;
if (filled) {
used.clear();
for (auto x : included) {
used.push_back(x);
move_outside(x);
}
included.clear();
}
if (eval(m) == k * m) {
l = m;
filled = false;
} else {
r = m;
filled = true;
}
}
return l;
}
