#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
vector<bool> already_tested(2020), ans(2020);
ll get_uniques(vector<ll> &v){
vector<ll> u;
for(ll i : v){
move_inside(i);
if(press_button() == 2) {
move_outside(i);
}
else u.push_back(i);
}
for(ll i: u) move_outside(i);
return u.size();
}
bool test(ll k, ll n, ll c, vector<bool> &info){
if(already_tested[k]) return ans[k];
vector<ll> v;
vector<bool> lol(n);
for(ll i = 0; i < n; i++) {
move_inside(i);
if(press_button() == k) {
v.push_back(i);
lol[i] = 1;
move_outside(i);
}
}
for(ll i = 0; i < n; i++) if(!lol[i]) move_outside(i);
already_tested[k] = 1; ans[k] = (get_uniques(v) == c);
return ans[k];
}
int min_cardinality(int n) {
vector<ll> v(n);
for(ll i = 0; i < n; i++) v[i] = i;
ll c = get_uniques(v);
vector<bool> info(n);
ll lo = 1, hi = n;
while(lo < hi){
ll mid = (lo + hi + 1) / 2;
if(test(mid, n, c, info)) lo = mid;
else hi = mid-1;
}
return lo;
}
