#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
int n = N;
vector<int> in(n);
vector<int> roots;
for (int i = 0; i < n; i++) {
move_inside(i);
if (press_button() == 2) {
move_outside(i);
} else {
roots.push_back(i);
in[i] = true;
}
}
assert((int) roots.size() > 0);
if ((int) roots.size() == 1) {
return n;
}
int base = (int) roots.size();
vector<int> possible;
for (int i = 0; i < n; i++) {
possible.push_back(i);
}
vector<int> max_value(n);
vector<int> min_value(n, 1234567);
auto Check = [&](int mid) {
vector<int> tmp;
for (int id = 0; id < (int) possible.size(); id++) {
int i = possible[id];
if (in[i] || max_value[i] > mid) {
continue;
}
move_inside(i);
if (min_value[i] < mid) {
tmp.push_back(i);
roots.push_back(i);
in[i] = true;
} else {
if (press_button() > mid) {
max_value[i] = max(max_value[i], mid);
move_outside(i);
} else {
min_value[i] = min(min_value[i], mid);
tmp.push_back(i);
roots.push_back(i);
in[i] = true;
}
}
}
if ((int) roots.size() == base * mid) {
sort(roots.begin(), roots.end());
return true;
}
possible = roots;
for (int i = 0; i < (int) tmp.size(); i++) {
roots.pop_back();
in[tmp[i]] = false;
move_outside(tmp[i]);
}
sort(roots.begin(), roots.end());
sort(possible.begin(), possible.end());
return false;
};
int low = 2;
int high = n / (int) roots.size();
while (low <= high) {
int mid = low + (high - low) / 2;
if (Check(mid)) {
low = mid + 1;
} else {
high = mid - 1;
}
}
--low;
return low;
}
