#include "insects.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
constexpr ll mod = 1'000'002'022;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define ln "\n"
struct union_find{
int N;
vi par;
union_find(int n): N(n){
par.resize(N);
rep(i,0,N) par[i] = i;
}
ll root(ll u){
if(par[u] == u) return u;
return par[u] = root(par[u]);
}
void merge(ll u, ll v){
u = root(u);
v = root(v);
if(u != v){
par[u] = v;
}
}
};
int min_cardinality(int N) {
union_find tree(N);
std::function<vi(ll,ll)> dfs = [&](ll l, ll r){
if(l+1 == r){
vi ret = {l};
return ret;
}
ll m = (l+r)/2;
vi L = dfs(l,m), R = dfs(m,r);
std::set<ll> nex;
{
vi nL, nR;
rep(i,0,L.size()) move_inside(L[i]);
rep(i,0,R.size()){
move_inside(R[i]);
if(press_button() == 1){
nex.insert(R[i]);
}
else{
nR.pb(R[i]);
}
move_outside(R[i]);
}
rep(i,0,L.size()) move_outside(L[i]);
rep(i,0,R.size()) move_inside(R[i]);
rep(i,0,L.size()){
move_inside(L[i]);
if(press_button() == 1){
nex.insert(L[i]);
}
else{
nL.pb(L[i]);
}
move_outside(L[i]);
}
rep(i,0,R.size()) move_outside(R[i]);
L = nL;
R = nR;
assert(L.size() == R.size());
}
if(L.size() > R.size()) std::swap(L,R);
ll sz = R.size();
vi left(sz), right(sz, L.size()+1);
while(true){
vi mid(sz,-1);
vii query(L.size()+1);
bool flag = false;
rep(i,0,sz){
if(left[i]+1 == right[i]) continue;
mid[i] = (left[i]+right[i])/2;
assert(1 <= mid[i] && mid[i] <= L.size());
query[mid[i]].pb(i);
flag = true;
}
if(!flag) break;
rep(i,0,L.size()){
move_inside(L[i]);
for(auto el: query[i+1]){
move_inside(R[el]);
ll val = press_button();
if(val == 2) right[el] = i+1;
else if(val == 1) left[el] = i+1;
else assert(false);
move_outside(R[el]);
}
}
rep(i,0,L.size()){
move_outside(L[i]);
}
}
for(auto el: L) nex.insert(el);
for(auto el: R) nex.insert(el);
rep(i,0,sz){
if(left[i] < L.size()){
tree.merge(L[left[i]], R[i]);
nex.erase(R[i]);
}
}
vi ret(all(nex));
/*cout << l << " " << r << " ";
for(auto el: L) cout << el << " ";
cout << " ";
for(auto el: R) cout << el << " ";
cout << " ";
rep(i,0,sz) cout << left[i] << " ";
cout << " ";
for(auto el: ret) cout << el << " ";
cout << endl;*/
return ret;
};
dfs(0,N);
vi cnt(N);
//rep(i,0,N) cout << tree.root(i) << endl;
rep(i,0,N) cnt[tree.root(i)]++;
ll min = N;
rep(i,0,N){
if(cnt[i]) min = std::min(min, cnt[i]);
}
return int(min);
}
