#include "insects.h"
#define here cerr<<"================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define pll pair<ll,ll>
#define popb pop_back
#define cer(a_) {cerr<<#a_<<": "<<endl; for(ll x_ : a_) cerr<<x_<< " "; cerr<<endl;}
using namespace std;
#define maxn 2005
ll n;
set<ll> s;
set<ll> last;
ll uniq = 0;
ll F[maxn];
ll cur = 0;
void add(ll i){
if(s.find(i)!=s.end()) return;
move_inside(i);
s.insert(i);
}
void del(ll i){
if(s.find(i)==s.end()){
cerr<<"out"<<endl;
return;
}
move_outside(i);
s.erase(i);
}
ll get(){return press_button();}
void klir(){
while(s.size()) del(*s.begin());
cur = 0;
}
vector<ll> newe;
ll f(ll x){
if(F[x]!=-1) return F[x];
cur = get();
if(cur>x){
while(newe.size()){
ll i = newe.back();
del(i);
newe.popb();
if(cur<x) break;
}
newe.clear();
return F[x] = s.size();
}
newe.clear();
for(ll i = 0;i<n;i++){
if(s.find(i)!=s.end()) continue;
add(i);
cur = get();
if(cur>x) del(i);
else newe.pb(i);
}
return F[x] = s.size();
}
ll min_cardinality(ll N) {
for(ll i = 0;i<maxn;i++) F[i] = -1;
n = N;
uniq = f(1);
klir();
//dbg(uniq);
ll rez = 0;
ll lg = 0,nn = 1;
while(nn<=n){nn*=2;lg++;}
for(ll j = lg-1;j>=0;j--){
//dbg(j);
if(f(rez+(1<<j))==(rez+(1<<j))*uniq) rez+=(1<<j);
else{
//here;
//cer(s);
}
}
return rez;
}
/**
6
5 8 9 5 9 9
**/
