#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i < b; i++)
using vi = vector<int>;
struct DSU {
int n; vi par, siz;
DSU() {};
DSU(int N) {
n = N;
par.resize(n); iota(par.begin(), par.end(), 0);
siz.assign(n, 1);
}
int find(int v) {
if (par[v] == v) return v;
return par[v] = find(par[v]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (siz[a] < siz[b]) swap(a, b);
par[b] = a;
siz[a] += siz[b];
}
}
};
int n;
DSU dsu;
set<int> dac(int l, int r) {
if (l + 1 == r) return set<int>({l});
int m = l + (r - l) / 2;
set<int> left = dac(l, m), right = dac(m, r);
set<int> used_right;
for (auto &el : left) {
move_inside(el);
for (auto &rel : right) {
if (used_right.count(rel)) continue;
move_inside(rel);
int press_ans = press_button();
move_outside(rel);
if (press_ans > 1) {
used_right.insert(rel);
dsu.unite(el, rel);
break;
}
}
move_outside(el);
}
set<int> ans;
for (auto &el : left) ans.insert(dsu.find(el));
for (auto &el : right) ans.insert(dsu.find(el));
return ans;
}
int min_cardinality(int N) {
n = N;
dsu = DSU(n);
dac(0, n);
return dsu.siz[*min_element(dsu.par.begin(), dsu.par.end(), [&](int a, int b) {
return dsu.siz[dsu.find(a)] < dsu.siz[dsu.find(b)];
})];
}
