#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
set<int> inside;
map<int, set<int>> states;
int D = 0;
vector<int> a;
void move_in(int x){
if(inside.count(x)) return;
move_inside(a[x]);
inside.insert(x);
}
void move_out(int x){
if(!inside.count(x)) return;
move_outside(a[x]);
inside.erase(x);
}
int min_cardinality(int N) {
a.resize(N);
iota(a.begin(), a.end(), 0);
shuffle(a.begin(), a.end(), rng);
for (int i = 0; i < N; ++i) {
D += 1;
move_in(i);
if (press_button() > 1) {
move_out(i);
D -= 1;
}
}
states[1] = inside;
for(int i = 0 ; i < N; ++i) states[N].insert(i);
// clear
for (int i = 0; i < N; ++i)
move_out(i);
// N log N
int l = 1, r = N / D, ans = 1;
while (l <= r) {
int mid = (l + r) / 2;
vector<int> last_inserted;
auto it = *states.lower_bound(mid);
for (int i : it.second) {
if ((int)inside.size() >= mid * D) break;
if (!inside.count(i)) {
move_in(i);
if (press_button() > mid)
move_out(i);
else
last_inserted.push_back(i);
}
}
cerr << "(cnt = " << inside.size() << ", mid = " << mid << ", d = " << D << ")\n";
states[mid] = inside;
if ((int)inside.size() >= mid * D) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
for(int i : last_inserted) move_out(i);
}
}
return ans;
}
