#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, met;
const int MAXN=2001;
bool ins[MAXN];
ll memo[MAXN];
bool can(ll x)
{
if(memo[x]!=0)
{
if(memo[x]==1)
return 0;
return 1;
}
ll i, cant=met;
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];
met=cant;
memo[x]=2;
return 1;
}
for(i=0; i<n; i++)
{
if(ag[i])
move_outside(i);
}
memo[x]=1;
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);
if(tam==1)
return N;
else if(tam==2)
{
for(i=0; i<n; i++)
{
if(ins[i]==1)
continue;
move_inside(i);
}
return N-press_button();
}
met=tam;
ll l=2, r=n/tam, m1, m2, pos=1;
while(l<=r)
{
m1=(l+(r-l)/3);
m2=(r-(r-l)/3);
if(can(m2))
{
l=m2+1;
pos=m2;
}
else if(can(m1))
l=m1+1;
else
r=m1-1;
}
return int(pos);
}
