#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 = 0;
set<int> s;
rep(b, 1, 2) {
rep(i, 0, N) {
move_inside(i);
in++;
int a = press_button();
if (a > b) {
move_outside(i);
in--;
s.insert(i);
}
else {
d++;
}
}
}
int l = 1, r = N/d+1;
int ans = 1;
set<int> never, use;
while (l <= r) {
int m = l+(int)(0.52*(r-l));
v<int> getout;
set<int> sm, nev;
for (auto x : s) {
if (never.count(x)) continue;
getout.push_back(x);
move_inside(x);
in++;
int a = press_button();
if (a > m) {
in--;
move_outside(x);
nev.insert(x);
}
else {
sm.insert(x);
}
}
for (auto x : getout) s.erase(x);
for (auto x : nev) s.insert(x);
if (in == m*d) {
ans = m;
l = m+1;
for (auto x : nev) s.insert(x);
rep(i, 0, N) {
if (!s.count(i)) use.insert(i);
}
}
else {
r=m-1;
for (auto x : nev) never.insert(x);
for (auto x : sm) {
if (!use.count(x)) {
move_outside(x);
s.insert(x);
in--;
}
}
}
}
return ans;
}
