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