#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> p;
int pressButton() {
return press_button();
}
void moveInside(int i) {
move_inside(p[i]);
}
void moveOutside(int i) {
move_outside(p[i]);
}
int ok(int N, int X) {
vector<int> A, B;
for (int i = 0; i < N; i++) {
moveInside(i);
int T = pressButton();
if (T >= X) {
moveOutside(i);
B.emplace_back(i);
}
}
for (int i : B) {
moveInside(i);
int T = pressButton();
if (T > X) {
moveOutside(i);
A.emplace_back(i);
}
}
int diff = int(B.size()) - int(A.size());
return diff * X < N - int(A.size());
}
int min_cardinality(int N) {
p.assign(N, 0);
iota(p.begin(), p.end(), 0);
shuffle(p.begin(), p.end(), rng);
int lo = 1, hi = N+1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (ok(N, mid)) hi = mid;
else lo = mid;
if (lo >= N/2) {
for (int i = 0; i < N; i++) moveInside(i);
int T = pressButton(), Z = N-T;
if (Z == 0) Z = INT_MAX;
return min(T, Z);
}
if (lo != hi) for (int i = 0; i < N; i++) moveOutside(i);
}
return lo;
}
