#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int n) {
int k = 0;
vector<int> r;
for (int i = 0; i < n; i++) {
move_inside(i);
if (press_button() > 1)
move_outside(i), r.push_back(i);
else
k++;
}
int l = k == 1 ? n : 1, u = n / k + 1, c = k;
while (l + 1 < u) {
int m = (l + u + 1) / 2;
vector<int> s, h;
for (int i : r) {
move_inside(i);
if (press_button() > m)
move_outside(i), h.push_back(i);
else
c++, s.push_back(i);
}
if (c == k * m) {
l = m;
r = h;
} else {
u = m;
for (int i : s)
c--, move_outside(i);
r = s;
}
}
return l;
}
