#include "insects.h"
#define dbg(x) cerr<<#x<<": "<<x<<endl
#include <bits/stdc++.h>
#define ll int
#define pll pair<ll,ll>
using namespace std;
#define maxn 2005
ll n;
set<ll> s;
ll uniq = 0;
ll a[maxn];
ll F[maxn];
bool ok[maxn];
ll val[maxn];
ll cur = 0;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void add(ll i){
if(s.find(i)!=s.end()) return;
move_inside(a[i]);
s.insert(i);
}
void del(ll i){
if(s.find(i)==s.end()){
cerr<<"out"<<endl;
return;
}
move_outside(a[i]);
s.erase(i);
}
ll get(){return press_button();}
void klir(){
while(s.size()) del(*s.begin());
}
set<ll> newe;
bool bad[maxn];
ll f(ll x){
if(F[x]!=-1) return F[x];
cur = get();
newe.clear();
for(ll i = 0;i<n;i++){
if(bad[i]) continue;
add(i);
cur = get();
if(cur>x) del(i);
else newe.insert(i);
}
return F[x] = s.size();
}
ll min_cardinality(ll N) {
for(ll i = 0;i<maxn;i++) F[i] = -1;
n = N;
for(ll i = 0;i<n;i++) a[i] = i;
shuffle(a,a+n,rng);
for(ll i = 0;i<n;i++) ok[i] = 1;
uniq = f(1);
for(ll x : s) bad[x] = 1;
//dbg(uniq);
ll l = 1, r = n/uniq,mid,rez = n;
while(l<=r){
mid = (l+r)/2;
if(f(mid)==uniq*mid) l = mid+1,rez = mid;
else{
r = mid-1;
for(ll i = 1;i<=n;i++){
if(s.find(i)!=s.end()) bad[i] = 1;
}
for(ll x : newe) del(x);
}
}
return rez;
}
/**
6
5 8 9 5 9 9
**/
