#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
const int LOG = 12;
int n;
vector<set<int>> active(LOG);
vector<int> v;
void build(int lb, int rb, int level){
if(lb>=rb) return;
int mb = (lb + rb) / 2;
for(int i=lb; i<=mb; i++){
active[level].insert(v[i]);
}
build(lb, mb, level+1);
build(mb+1, rb, level+1);
}
int min_cardinality(int N) {
n = N;
vector<int> rest;
for(int i=0; i<n; i++){
move_inside(i);
v.push_back(i);
if(press_button()>=2){
move_outside(i);
v.pop_back();
rest.push_back(i);
}
}
build(0, v.size()-1, 0);
int m=n-v.size();
vector<int> lb(m), rb(m, v.size()-1), count(v.size(), 1);
set<int> cur(v.begin(), v.end());
for(int level=0; level<LOG; level++){
// activate
for(auto x:active[level]){
if(not cur.count(x)){
cur.insert(x);
move_inside(x);
}
}
auto c_cur=cur;;
// deactivate
for(auto x:c_cur){
if(not active[level].count(x)){
cur.extract(x);
move_outside(x);
}
}
// query
for(int i=0; i<m; i++){
if(lb[i]>=rb[i]) continue;
int mb = (lb[i] + rb[i])/2;
move_inside(rest[i]);
if(press_button()==2){
rb[i]=mb;
}else{
lb[i]=mb+1;
}
move_outside(rest[i]);
}
}
for(int i=0; i<m; i++){
count[lb[i]]++;
}
return *min_element(count.begin(), count.end());
}
