#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int n) {
vector<int> st, vis(n), a(n);
st.push_back(0);
int id = 1;
for(int i=1; i<n; i++) {
int l=0, r=st.size()-1, p=-1;
move_inside(i);
while(l <= r) {
int mid = (l + r) / 2;
for(int j=0; j<n; j++) {
if(vis[j]) move_outside(j);
}
for(int j=mid; j<st.size(); j++) {
vis[st[j]] = 1;
move_inside(st[j]);
}
if(press_button() == 2) p = mid, l = mid + 1;
else r = mid - 1;
}
move_outside(i);
if(p == -1) {
st.push_back(i);
a[i] = id++;
} else {
a[i] = a[st[p]];
}
}
vector<int> cnt(n);
for(int i=0; i<n; i++) cnt[a[i]]++;
int mn = n;
for(int i=0; i<n; i++)
if(cnt[i]) mn = min(mn, cnt[i]);
return mn;
}
