#include"insects.h"
#include<bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
vector<int> Ls{0}, cnt(N, 1);
move_inside(0);
set<int> ins{0};
for(int i = 1; i < N; ++i) {
move_inside(i);
ins.insert(i);
int ks = press_button();
if(ks == 1) { Ls.push_back(i); continue; }
int tl = 0, tr = (int)Ls.size();
while(tl < tr) {
int tm = (tl + tr) / 2;
for(int j = tl; j <= tm; ++j) { if(ins.find(Ls[j]) != end(ins)) { move_outside(Ls[j]); ins.erase(Ls[j]); } }
if(press_button() == 2) {
tl = tm + 1;
} else {
tr = tm;
tm = (tl + tr) / 2;
for(int j = tm + 1; j <= tr; ++j) {
if(ins.insert(Ls[j]).second) move_inside(Ls[j]);
}
}
}
++cnt[Ls[tl]];
for(auto& u : Ls) if(ins.insert(u).second) move_inside(u);
ins.erase(i);
move_outside(i);
}
int ans = 0x3f3f3f3f;
for(auto& u : Ls) ans = min(ans, cnt[u]);
return ans;
}
