#include "insects.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <variant>
#include <map>
#include <random>
#include <chrono>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randint(int l, int r) {return uniform_int_distribution<int>(l, r)(rng);}
struct DisjointSetUnion {
int n;
vector<int> fa, sz;
DisjointSetUnion(int _n) : n(_n), fa(n), sz(n, 1) {iota(fa.begin(), fa.end(), 0);}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int size(int x) {
return sz[find(x)];
}
bool same(int x, int y) {
return find(x) == find(y);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
fa[y] = x;
sz[x] += sz[y];
}
};
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N) {
int n = N;
vector<int> p(n);
iota(p.begin(), p.end(), 0);
shuffle(p.begin(), p.end(), rng);
DisjointSetUnion dsu(n);
int ans = n;
auto solve = [&] (auto solve, vector<int> p) -> vector<int> {
int n = p.size();
if (n <= 1) return p;
int threshold = 4;
if (n >= threshold) {
vector<int> vl, vr;
for (int x: p) {
move_inside(x);
if (press_button() == 2) {
move_outside(x);
vr.push_back(x);
}else{
vl.push_back(x);
}
}
for (int x: vl) {
move_outside(x);
}
vector<int> r1(vr.begin(), vr.begin() + vr.size() / 2);
vector<int> r2(vr.begin() + vr.size() / 2, vr.end());
vr = solve(solve, r2);
vr.insert(vr.end(), r1.begin(), r1.end());
shuffle(vl.begin(), vl.end(), rng);
shuffle(vr.begin(), vr.end(), rng);
vector<int> arr = vl;
int ptr = 0;
auto move_pointer_to = [&] (int tar) {
while (ptr < tar) move_inside(arr[ptr++]);
while (ptr > tar) move_outside(arr[--ptr]);
};
vector<int> rem = vr;
auto search = [&] (auto search, int ql, int qr, vector<int> uq) -> void {
if (!uq.size()) return;
if (ql == qr) {
for (int x: uq) dsu.merge(arr[ql], x);
return;
}
vector<int> ul, ur;
int qm = ql + qr >> 1;
move_pointer_to(qm + 1);
for (int x: uq) {
move_inside(x);
if (press_button() == 2) {
ul.push_back(x);
}else{
ur.push_back(x);
}
move_outside(x);
}
search(search, qm+1, qr, ur);
search(search, ql, qm, ul);
};
search(search, 0, arr.size() - 1, rem);
move_pointer_to(0);
}else{
vector<int> v;
for (int x: p) {
bool uni = true;
if (v.size()) {
move_inside(x);
for (int y: v) {
move_inside(y);
bool sm = press_button() == 2;
move_outside(y);
if (sm) {dsu.merge(x, y); uni = false; break;}
}
move_outside(x);
}
if (uni) v.push_back(x);
}
}
vector<int> res;
for (int x: p) if (dsu.find(x) == x) res.push_back(x);
return res;
};
solve(solve, p);
for (int i=0; i<n; i++) ans = min(ans, dsu.size(i));
return ans;
}
