#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();
ll n, tam;
const int MAXN=2001;
bool ins[MAXN];
bool can(ll x)
{
ll i, cant=tam;
vector<bool>ag(n);
for(i=0; i<n; i++)
{
if(ins[i])
continue;
move_inside(i);
if(press_button()>x)
move_outside(i);
else
{
ag[i]=1;
cant++;
}
}
bool ans=0;
if(cant==tam*x)
{
for(i=0; i<n; i++)
ins[i]=ins[i]|ag[i];
return 1;
}
for(i=0; i<n; i++)
{
if(ag[i])
move_outside(i);
}
return 0;
}
int min_cardinality(int N)
{
ll i;
n=N;
vector<ll>v;
move_inside(0);
v.pb(0);
ins[0]=1;
for(i=1; i<n; i++)
{
move_inside(i);
if(press_button()==1)
{
v.pb(i);
ins[i]=1;
}
else
move_outside(i);
}
tam=sz(v);
ll l=2, r=n/tam, piv, pos=1;
while(l<=r)
{
piv=(l+r)/2;
if(can(piv))
{
l=piv+1;
pos=piv;
}
else
r=piv-1;
}
return int(pos);
}
