#include <bits/stdc++.h>
#define ll long long
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand_index(int n) {
return abs((ll)rng()) % n + 1;
}
vector<int> current;
int total;
void move_inside(int);
void move_outside(int);
int press_button();
void insert(int i) {
for (int x : current)
if (x == i) return;
move_inside(i);
current.push_back(i);
}
void erase(int i) {
auto it = find(current.begin(), current.end(), i);
if (it != current.end()) {
move_outside(i);
current.erase(it);
}
}
int press() {
return press_button();
}
void shuffle_vec(vector<int>& v) {
for (int i = 0; i < v.size(); ++i)
swap(v[i], v[rand_index(v.size()) - 1]);
}
int min_cardinality(int N) {
total = N;
vector<int> pool, stable;
bool keep = true;
for (int i = 0; i < total; ++i) {
insert(i);
pool.push_back(i);
if (i && press() > 1)
erase(i);
}
int base = current.size();
stable = current;
if (base == 1) {
current.clear();
return total;
}
int low = 1, high = total / base + 1;
while (low + 1 < high) {
int mid = (low + high) / 2;
shuffle_vec(pool);
if (!keep) {
for (int x : pool)
if (find(stable.begin(), stable.end(), x) == stable.end())
erase(x);
}
for (int i = 0; i < pool.size(); ++i) {
if ((int)current.size() == base * mid) break;
int before = current.size();
insert(pool[i]);
if ((int)current.size() > before && press() > mid)
erase(pool[i]);
}
if ((int)current.size() == base * mid) {
low = mid;
stable = current;
keep = true;
} else {
high = mid;
pool = current;
keep = false;
}
}
current.clear();
return low;
}
