#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
using ll = long long;
#define rep(i, k, n) for (int i = k; i < n; i++)
int min_cardinality(int N) {
int in = 0;
int d;
v<int> gr;
rep(b, 1, 2) {
rep(i, 0, N) {
move_inside(i);
in++;
int a = press_button();
if (a > b) {
move_outside(i);
in--;
}
if (a == b && b == 1) {
gr.push_back(i);
}
}
if (b == 1) d = in;
for (auto x : gr) {
move_outside(x);
}
}
int l = 0, r = N;
int ans = N;
map<int, int> mp;
mp.clear();
while (l <= r) {
int m = (l+r)/2;
in = 0;
v<int> getout;
rep(i, 0, N) {
if (mp.count(i)) continue;
move_inside(i);
int a = press_button();
if (a > m) {
move_outside(i);
}
else {
getout.push_back(i);
in++;
mp[i]++;
}
}
if (in == m*d) {
ans = m;
l = m+1;
}
else {
r = m-1;
for (auto x : getout) {
move_outside(x);
mp.erase(x);
}
}
}
return ans;
}
