#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;
map<int, int> mp;
rep(b, 1, 2) {
rep(i, 0, N) {
move_inside(i);
int a = press_button();
if (a > b) {
move_outside(i);
}
else {
mp[i]++;
in++;
}
}
if (b == 1) d = in;
}
int l = 1, r = N;
int ans = 1;
while (l <= r) {
int m = (l+r)/2;
v<int> getout;
//cout << m << ": ";
rep(i, 0, N) {
if (mp.count(i)) continue;
if (in == m*d) continue;
move_inside(i);
//cout << i << " ";
int a = press_button();
if (a > m) {
move_outside(i);
//cout << 0 << ", ";
}
else {
getout.push_back(i);
in++;
mp[i]++;
//cout << 1 << ", ";
}
}
if (in == m*d) {
ans = m;
l = m+1;
}
else {
r = m-1;
for (auto x : getout) {
move_outside(x);
mp.erase(x);
in--;
}
}
//cout << endl;
}
return ans;
}
