#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi22/d2/debug.h"
#else
#define debug(...) void(37)
#endif
int min_cardinality(int N) {
vector<bool> in_set(N);
vector<bool> deact(N);
int cur = 0;
auto Move = [&](int x) {
if (x < cur) {
for (int i = 0; i < N; ++i) {
if (in_set[i]) {
in_set[i] = false;
move_outside(i);
}
}
}
for (int i = 0; i < N; ++i) {
if (!in_set[i] && !deact[i]) {
move_inside(i);
in_set[i] = true;
if (press_button() > x) {
move_outside(i);
in_set[i] = false;
}
}
}
cur = x;
return accumulate(in_set.begin(), in_set.end(), 0);
};
int K = Move(1);
debug(K);
int low = 2, high = (N / K) + 1;
while (low < high) {
int size = N - accumulate(deact.begin(), deact.end(), 0);
int mid = low;
int ls = K, rs = size - K;
while (ls + K <= rs - K) {
ls += K, rs -= K;
++mid;
}
int card = Move(mid);
debug(mid, card);
if (card == K * mid) {
low = mid + 1;
for (int i = 0; i < N; ++i) {
if (in_set[i]) {
deact[i] = true;
}
}
} else {
for (int i = 0; i < N; ++i) {
if (!in_set[i]) {
deact[i] = true;
}
}
high = mid;
}
}
return low - 1;
}
