#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();
int min_cardinality(int N)
{
ll i, act=0, n=N;
vector<ll>in,out,ins;
for(i=0; i<n; i++)
ins.pb(i);
for(auto k:ins)
{
move_inside(k);
if(press_button()>1)
{
move_outside(k);
out.pb(k);
}
else
{
in.pb(k);
act++;
}
}
if(act==1)
return N;
else if(act==2)
{
for(auto k:out)
move_inside(k);
return N-press_button();
}
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);
for(auto k:ins)
{
move_inside(k);
if(press_button()>piv)
{
move_outside(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)
{
move_outside(k);
act--;
}
ins=in;
}
}
return int(pos);
}
