#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, cant=0;
vector<ll>v(N,0);
for(i=N-1; i>=0; i--)
{
move_inside(i);
if(press_button()==1)
{
cant++;
v[i]=1;
}
else
move_outside(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++)
{
if(v[i]>=2)
{
fin++;
continue;
}
move_inside(i);
if(press_button()>=ma)
{
if(v[i])
{
v[i]=2;
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;
}
