#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
set<int> inside, active;
int U = 0;
for (int i = 0; i<N; i++){
active.insert(i);
}
vector<int> fnd;
for (auto u : active){
move_inside(u);
int x = press_button();
if (x > 1) move_outside(u);
else fnd.push_back(u);
}
U = fnd.size();
sort(fnd.begin(), fnd.end());
for (auto u : fnd) active.erase(u);
int lo = 1;
int hi = N/U;
int tot = U;
while (lo < hi){
int mid = (lo+hi+2)/2;
fnd.clear();
for (auto u : active){
move_inside(u);
int x = press_button();
if (x > mid) move_outside(u);
else{
fnd.push_back(u);
tot++;
}
if (tot == mid * U) break;
}
if (tot == mid * U){
lo = mid;
for (auto u : fnd) active.erase(u);
}
else if (tot < mid * U){
hi = mid-1;
active.clear();
for (auto u : fnd){
active.insert(u);
move_outside(u);
tot--;
}
}
}
return lo;
}
