#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
int min_cardinality(int N) {
int cnt = 0, add = 0;
unordered_set<int> unique;
for (int i = 0; i < N; i++) {
cnt++;
move_inside(i);
unique.insert(i);
int res = press_button();
if (res == 2) {
cnt--;
move_outside(i);
unique.extract(i);
}
}
int l = 0, r = N / cnt, curr = cnt;
while (r - l > 1) {
int m = (l + r) / 2;
unordered_set<int> ts;
for (int i = 0; i < N; i++) {
if (unique.count(i)) continue;
curr++;
move_inside(i);
int res = press_button();
if (res > m) {
curr--;
move_outside(i);
}
if (curr >= cnt * m) {
for (int j = i+1; j < N; j++) {
if (unique.count(i)) continue;
ts.insert(i);
}
break;
}
}
if (curr >= cnt * m) {
for (int i = 0; i < N; i++) {
unique.insert(i);
}
for (auto &x : ts) {
unique.extract(x);
}
r = m;
} else {
for (auto &x : ts) {
unique.insert(x);
}
for (int i = 0; i < N; i++) {
if (unique.count(i)) continue;
move_outside(i);
curr--;
}
l = m;
}
}
return r;
}
