#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000002022
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
bool czy[2007];
ll n;
void upd(ll a){
if(czy[a])move_outside(a);
else move_inside(a);
czy[a]^=1;
}
ll gt(){return press_button();}
vector<ll>al;
void sh(){
for(ll i=al.size()-1;i>=0;i--){
// swap(al[i],al[rand()%(i+1)]);
}
}
int min_cardinality(int NN){
al.clear();
for(ll i=0;i<NN;i++)czy[i]=0;
srand(15);
n=NN;
ll d=1;
for(ll i=0;i<n;i++)al.pb(i);
sh();
upd(al[0]);
vector<ll>v={al[0]},vpom;
for(ll i=1;i<n;i++){
upd(al[i]);
if(gt()==2){upd(al[i]);vpom.pb(al[i]);}
else {d++;v.pb(al[i]);}
}
if(d==1)return n;
al=vpom;
ll pocz=1;
ll kon=n/d;
while(pocz!=kon){
//cout<<kon<<" ";
ll mid=(pocz+kon+1+(1))/2;
sh();
ll ak=mid-pocz+d*pocz;
vector<ll>v1,v2,v3;
for(ll i=0;i<mid-pocz;i++){upd(al[i]);v2.pb(al[i]);}
for(ll i=mid-pocz;i<al.size();i++){
if(ak==mid*d){
v1.pb(al[i]);
continue;
}
if(ak+al.size()-i<mid*d){
v3.pb(al[i]);
continue;
}
upd(al[i]);
if(gt()==mid+1){upd(al[i]);v1.pb(al[i]);}
else {ak++;v2.pb(al[i]);}
}
if(ak==mid*d){
al=v1;
pocz=mid;
}
else{
al=v2;
for(ll i : v3)al.pb(i);
kon=mid-1;
for(ll i : v2)upd(i);
}
kon=min(kon,(ll)pocz+(ll)al.size()/d);
}
return pocz;
}
