#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng_engine(chrono::steady_clock::now().time_since_epoch().count());
int get_random(int range)
{
return (abs((long long)rng_engine()) % range) + 1;
}
vector<int> current_set;
int total_elements;
void move_inside(int);
void move_outside(int);
int press_button();
void insert_element(int index)
{
if (find(current_set.begin(), current_set.end(), index) != current_set.end())
return;
move_inside(index);
current_set.push_back(index);
}
void remove_element(int index)
{
auto it = find(current_set.begin(), current_set.end(), index);
if (it == current_set.end())
return;
move_outside(index);
current_set.erase(it);
}
int press()
{
return press_button();
}
void shuffle_elements(vector<int> &vec)
{
for (int i = 0; i < vec.size(); ++i)
swap(vec[i], vec[get_random((int)vec.size()) - 1]);
}
int min_cardinality(int N)
{
total_elements = N;
vector<int> all_elements, last_state;
bool using_last_state = true;
for (int i = 0; i < N; ++i)
{
insert_element(i);
all_elements.push_back(i);
if (i > 0 && press() > 1)
remove_element(i);
}
int base = current_set.size();
last_state = current_set;
if (base == 1)
return N;
int low = 1, high = N / base + 1;
while (low + 1 < high)
{
int mid = (low + high) / 2;
shuffle_elements(all_elements);
if (!using_last_state)
for (int x : all_elements)
if (find(last_state.begin(), last_state.end(), x) == last_state.end())
remove_element(x);
for (int i = 0; i < all_elements.size(); ++i)
{
if ((int)current_set.size() == base * mid)
break;
insert_element(all_elements[i]);
if ((int)current_set.size() > base * mid || press() > mid)
remove_element(all_elements[i]);
}
if ((int)current_set.size() == base * mid)
{
low = mid;
last_state = current_set;
using_last_state = true;
}
else
{
high = mid;
all_elements = current_set;
using_last_state = false;
}
}
current_set.clear();
return low;
}
