#include<bits/stdc++.h>
#include "insects.h"
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
int min_cardinality(int n){
vector<int>parent(n), size(n);
iota(parent.begin(), parent.end(), 0);
fill(size.begin(), size.end(), 1);
auto find_set = [&] (int N){
while(N != parent[N]){
N = parent[N] = parent[parent[N]];
}
return N;
};
auto merge = [&] (int u, int v){
if((u = find_set(u)) != (v = find_set(v))){
if(size[u] < size[v]){
swap(u, v);
}
size[parent[v] = u] += size[v];
}
};
vector<int>d, s, low, high, p;
for(int i = 0; i < n; i++){
move_inside(i);
if(press_button() == 2){
move_outside(i);
s.emplace_back(i);
low.emplace_back(0);
high.emplace_back(int(d.size()) - 1);
}
else{
d.emplace_back(i);
}
}
p.resize(s.size());
int cur_pos = int(d.size()) - 1;
while(true){
int min_low = n, max_high = -1;
vector<vector<int>>query(d.size());
for(int i = 0; i < s.size(); i++){
if(low[i] <= high[i]){
int mid = (low[i] + high[i]) >> 1;
minimize(min_low, low[i]);
maximize(max_high, high[i]);
query[mid].emplace_back(i);
}
}
if(max_high == -1){
break;
}
if(cur_pos >= max_high){
for(int i = cur_pos; i >= min_low; move_outside(d[i--])){
for(int& j : query[i]){
move_inside(s[j]);
if(press_button() == 2){
p[j] = d[i];
high[j] = i - 1;
}
else{
low[j] = i + 1;
}
move_outside(s[j]);
}
}
cur_pos = min_low - 1;
}
else{
for(int i = cur_pos + 1; i <= max_high; i++){
move_inside(d[i]);
for(int& j : query[i]){
move_inside(s[j]);
if(press_button() == 2){
p[j] = d[i];
high[j] = i - 1;
}
else{
low[j] = i + 1;
}
move_outside(s[j]);
}
}
cur_pos = max_high;
}
}
for(int i = 0; i < s.size(); i++){
merge(s[i], p[i]);
}
int ans = n;
for(int i = 0; i < n; i++){
minimize(ans, size[find_set(i)]);
}
return ans;
}
