#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
long long n;
bitset<2069> ca,spc;
inline void ins(long long x)
{
ca[x]=1;
move_inside(x);
}
inline void ers(long long x)
{
ca[x]=0;
move_outside(x);
}
inline long long qr()
{
return press_button();
}
inline long long op(long long x)
{
long long i,c=0;
for(i=0;i<n;i++)
{
if(ca[i]&&!spc[i])
{
ers(i);
}
}
for(i=0;i<n;i++)
{
if(!spc[i])
{
ins(i);
if(qr()>x)
{
ers(i);
}
}
c+=ca[i];
}
return c;
}
int min_cardinality(int on)
{
long long i,k,c,lh,rh,md,zz;
n=on;
c=op(1);
if(c==1)
{
return n;
}
for(zz=1,lh=2,rh=n/c;lh<=rh;)
{
md=(lh+rh)/2;
k=op(md);
if(k==md*c)
{
zz=md;
lh=md+1;
for(i=0;i<n;i++)
{
if(ca[i])
{
spc[i]=1;
}
}
}
else
{
rh=md-1;
for(i=0;i<n;i++)
{
if(!ca[i])
{
spc[i]=1;
}
}
}
}
return zz;
}
