#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()
{
ll x=memo[en];
if(x)
return x;
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];
}
}
x=memo[vis];
if(x)
return x;
x=press_button();
memo[vis]=x;
return x;
}
int min_cardinality2(int N, ll cant)
{
ll i;
vector<ll>v(N,0);
for(i=0; i<N; i++)
v[i]=en[i];
for(i=0; i<N; i++)
if(v[i])
move_outside(i);
ll ma=N/cant, fin;
while(true)
{
vector<ll>in;
fin=0;
for(i=0; i<N; i++)
{
move_inside(i);
if(press_button()>=ma)
{
if(v[i])
fin++;
move_outside(i);
}
else
in.pb(i);
}
if(fin==cant)
return int(ma);
ll M=sz(in)-fin*(ma-1);
ma=M/(cant-fin);
for(i=0; i<sz(in); i++)
move_outside(in[i]);
}
return 0;
}
int min_cardinality(int N)
{
ll i, act = 0;
n = N;
vis.resize(N, 0);
en.resize(N, 0);
vector<ll> in, out, ins;
for (i = 0; i < n; i++)
ins.pb(i);
mi(0);
in.pb(0);
act++;
for (auto k : ins)
{
if(k==0)
continue;
mi(k);
if (pBtn() > 1)
{
mo(k);
out.pb(k);
}
else
{
in.pb(k);
act++;
}
}
if(act<=10)
{
if(in.back()!=ins.back())
move_outside(ins.back());
return min_cardinality2(N,act);
}
ll l = 2, r = n / act, piv, pos = 1, tot = act;
ins = out;
while (l <= r)
{
piv = (l + r) / 2;
in.resize(0);
out.resize(0);
ll init=ins[0];
if(sz(ins)!=1)
{
mi(init);
in.pb(init);
act++;
}
else
init=-1;
for (auto k : ins)
{
if(k==init)
continue;
mi(k);
if (pBtn() > piv)
{
mo(k);
out.pb(k);
}
else
{
in.pb(k);
act++;
}
}
if (act == tot * piv)
{
l = piv + 1;
pos = piv;
ins = out;
}
else
{
r = piv - 1;
for (auto k : in)
{
mo(k);
act--;
}
ins = in;
}
}
return int(pos);
}
