#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int ok(int N, int X) {
for (int i = 0; i < N; i++) move_outside(i);
vector<int> A, B;
for (int i = 0; i < N; i++) {
move_inside(i);
int T = press_button();
if (T > X) {
move_outside(i);
A.emplace_back(i);
}
}
for (int i = 0; i < N; i++) move_outside(i);
for (int i = 0; i < N; i++) {
move_inside(i);
int T = press_button();
if (T >= X) {
move_outside(i);
B.emplace_back(i);
}
}
int diff = int(B.size()) - int(A.size());
return diff * X < N - int(A.size());
}
int min_cardinality(int N) {
int lo = 1, hi = N+1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (ok(N, mid)) hi = mid;
else lo = mid;
}
return lo;
}
