#include"insects.h"
#include<bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
int k;
int D = 0;
set<int> INs;
for(int i = 0; i < N; ++i) {
INs.insert(i);
move_inside(i);
k = press_button();
if(k == 2) {
INs.erase(i);
move_outside(i);
continue;
}
++D;
}
int tl = 1, tr = N / D;
while(tl < tr) {
int tm = (tl + tr + 1) / 2;
for(int i = 0; i < N; ++i) {
if(!INs.insert(i).second) continue;
move_inside(i);
k = press_button();
if(k > tm) {
INs.erase(i);
move_outside(i);
continue;
}
if(D * tm == (int)INs.size()) break;
}
if((int)INs.size() < D * tm) {
tr = tm - 1;
if(tl == tr) continue;
tm = (tl + tr + 1) / 2;
for(int i = N - 1; i >= 0; --i) {
if(INs.find(i) == end(INs)) continue;
k = press_button();
if(k > tm) {
INs.erase(i);
move_outside(i);
} else break;
}
} else {
tl = tm;
}
}
return (tl + tr) / 2;
}
