#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
vector<bool> vis, en;
map<vector<bool>, ll> memo;
ll n;
void mi(ll x){ en[x]=1; }
void mo(ll x){ en[x]=0; }
ll pBtn(){
if(memo.count(en)) return memo[en];
for(ll i=0;i<sz(en);i++){
if(vis[i]!=en[i]){
if(vis[i]) move_outside(i);
else move_inside(i);
vis[i]=en[i];
}
}
ll x=press_button();
memo[vis]=x;
return x;
}
int min_cardinality(int N){
n=N;
vis.assign(N,0);
en.assign(N,0);
vector<ll> in,out,ins;
for(ll i=0;i<n;i++) ins.pb(i);
mi(0);
in.pb(0);
ll act=1;
for(auto k:ins){
if(k==0) continue;
mi(k);
if(pBtn()>1){
mo(k);
out.pb(k);
}else{
in.pb(k);
act++;
}
}
ll tot=act;
ll l=1, r=n/tot, pos=1;
ins=out;
while(l<=r){
ll piv=(l+r+1)/2;
in.clear();
out.clear();
ll act_now=tot;
for(auto k:ins){
mi(k);
if(pBtn()>piv){
mo(k);
out.pb(k);
}else{
in.pb(k);
act_now++;
}
}
if(act_now==tot*piv){
pos=piv;
l=piv+1;
ins=out;
}else{
r=piv-1;
for(auto k:in) mo(k);
ins=in;
}
}
return int(pos);
}
