#include <bits/stdc++.h>
void move_inside(int i);
void move_outside(int i);
int press_button();
using namespace std;
int min_cardinality(int N) {
vector<int> p(N);
iota(p.begin(), p.end(), 0);
mt19937 gen(random_device{}());
shuffle(p.begin(), p.end(), gen);
auto add = [&](int i) { move_inside(p[i]); };
auto remove = [&](int i) { move_outside(p[i]); };
vector<int> used(N);
for (int i = 0; i < N; ++i) {
add(i);
used[i] = 1;
if (press_button() > 1) {
remove(i);
used[i] = 0;
}
}
int num_elems = accumulate(used.begin(), used.end(), 0);
int n = N;
vector<int> idxs(n);
iota(idxs.begin(), idxs.end(), 0);
int lo = 1, hi = n / num_elems;
while (lo < hi) {
int mi = (lo + hi + 1) / 2;
vector<int> stk;
for (int i = 0, cnt = accumulate(used.begin(), used.end(), 0); i < n; ++i) {
if (used[idxs[i]] || cnt + int(stk.size()) == mi * num_elems) {
continue;
}
stk.push_back(idxs[i]);
add(idxs[i]);
if (press_button() > mi) {
remove(idxs[i]);
stk.pop_back();
}
}
if (accumulate(used.begin(), used.end(), 0) + int(stk.size()) == mi * num_elems) {
lo = mi;
for (int &i : stk) {
used[i] = 1;
}
} else {
hi = mi - 1;
for (int &i : stk) {
remove(i);
}
idxs = stk;
for (int i = 0; i < N; ++i) {
if (used[i]) {
idxs.push_back(i);
}
}
n = idxs.size();
hi = min(hi, n / num_elems);
}
}
return lo;
}
