#include "insects.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#ifdef DEBUG
auto& operator<<(auto& os, pair<auto, auto> &p) {
return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto& os, const auto &v) {
os<<"{";
for(auto it=begin(v);it!=end(v);++it) {
if(it != begin(v)) os<<", ";
os<<(*it);
}
return os<<"}";
}
void dbg_out(auto... x) {
((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif
int n;
vi perm;
vi added;
void in(int i) {
if(added[i]) return;
added[i] = true;
move_inside(perm[i]);
}
void out(int i) {
if(!added[i]) return;
added[i] = false;
move_outside(perm[i]);
}
int button() {
int res = press_button();
dbg(added, res);
return res;
}
vi dsu, siz;
int find(int x) {
if(dsu[x] == x) return x;
return dsu[x] = find(dsu[x]);
}
void merge(int a, int b) {
dbg("merge", a, b);
a = find(a); b = find(b);
if(a == b) return;
if(siz[a] < siz[b]) swap(a, b);
siz[a] += siz[b];
dsu[b] = a;
}
vi merge_dsu(vi a, vi b) {
if(sz(a) < sz(b)) swap(a, b);
vector<tuple<int,int,int>> bin;
for(auto x : a) in(x);
rep(i,0,sz(b)) {
in(b[i]);
if(button() != 1) {
bin.emplace_back(0,sz(a)-1,i);
}
out(b[i]);
}
while(!bin.empty()) {
sort(all(bin));
pii last = {-1, -1};
vector<tuple<int,int,int>> new_bin;
for(auto [l,r,ind] : bin) {
dbg(l, r, ind);
if(l == r) {
merge(a[l], b[ind]);
continue;
}
int mid = (l + r + 1) / 2;
if(make_pair(l, r) != last) {
rep(i,0,sz(a)) {
if(l <= i && i < mid) in(a[i]);
else out(a[i]);
}
last = {l, r};
}
in(b[ind]);
if(button() == 1)
l = mid;
else
r = mid - 1;
out(b[ind]);
new_bin.emplace_back(l, r, ind);
}
bin = new_bin;
}
rep(i,0,sz(a))
out(a[i]);
set<int> s;
rep(i,0,sz(a)) s.insert(find(a[i]));
rep(i,0,sz(b)) s.insert(find(b[i]));
dbg(a, b, s);
return vi(all(s));
}
vi solve(int l, int r) {
if(l == r) return {l};
int mid = (l + r) / 2;
auto a = solve(l, mid);
auto b = solve(mid+1, r);
auto res = merge_dsu(a, b);
dbg(l, r, res);
return res;
}
int min_cardinality(int N) {
n = N;
perm.resize(n);
iota(all(perm), 0);
// random_shuffle(all(perm));
added.assign(n, 0);
siz.assign(n, 1);
dsu.resize(n);
iota(all(dsu), 0);
solve(0, n-1);
dbg(dsu);
dbg(siz);
int mini = n;
rep(i,0,n)
mini = min(mini, siz[find(i)]);
return mini;
}
