#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 polySolution(int N) {
for (int i = 0; i < N; i++) moveInside(i);
vector<int> inside, outside;
inside.resize(N);
iota(inside.begin(), inside.end(), 0);
while (1) {
int X = pressButton();
if (X == 1 || X == inside.size()) return X;
for (int i : inside) {
moveOutside(i);
int T = pressButton();
if (T == X) {
moveOutside(i);
outside.emplace_back(i);
}
else moveInside(i);
}
for (int i : inside)
if (!binary_search(outside.begin(), outside.end(), i)) moveOutside(i);
for (int i : outside) moveInside(i);
swap(outside, inside);
outside.clear();
}
}
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/6) {
return polySolution(N);
}
if (lo != hi) for (int i = 0; i < N; i++) moveOutside(i);
}
return lo;
}
