#include<bits/stdc++.h>
#define ll long long
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int n){
long long x = rng();
return abs(x) % n + 1;
}
vector<int> ps;
int n , dst;
void move_inside(int i);
void push(int i){
int p = -1;
for(int j = 0;j < ps.size(); ++ j) if(ps[j] == i) p = j;
if(p != -1) return ;
move_inside(i);
ps.push_back(i);
}
void move_outside(int i);
void remove(int i){
int p = -1;
for(int j = 0;j < ps.size(); ++ j) if(ps[j] == i) p = j;
if(p == -1) return ;
move_outside(i);
ps.erase(ps.begin() + p , ps.begin() + p + 1);
}
int press_button();
int press() {return press_button(); }
void shufle(vector<int> &v){
int sz = v.size();
for(int i = 0;i < sz; ++ i) swap(v[i] , v[rand(sz) - 1]);
}
int min_cardinality(int N){
n = N;
vector<int> v , ls;
bool pre = true;
for(int i = 0;i < n; ++ i){
push(i);
v.push_back(i);
if(i and press() > 1) remove(i);
}
int ds = ps.size() ;
ls = ps;
if(ds == 1) return n;
int l = 1;
int r = n / ds + 1;
while(l + 1 < r){
int mid = (l + r) / 2;
shufle(v);
if(! pre){
for(auto to : v){
bool w = false;
for(auto it : ls) if(to == it) w = true;
if(! w) remove(to);
}
}
for(int i = 0;i < v.size(); ++ i){
int sz = ps.size();
if(sz == ds * mid) break;
push(v[i]);
if(sz != ps.size() and press() > mid) remove(v[i]);
}
if(ps.size() == ds * mid){
l = mid;
ls = ps;
pre = true;
}
else{
r = mid;
v = ps;
pre = false;
}
}
ps.clear();
return l;
}
