#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define get press_button
set<int> se;
void add(int u)
{
if (se.count(u)) return;
move_inside(u), se.insert(u);
}
void rem(int u)
{
if (!se.count(u)) return;
move_outside(u), se.erase(u);
}
int min_cardinality(int n)
{
vector<int> v={0};
add(0);
for (int i=1;i<n;i++)
{
add(i),v.push_back(i);
if (get()==2)
rem(i),v.pop_back();
}
if (v.size()>250)
{
bool vis[n]={};
int ans=0, t=v.size();
while (1)
{
ans++;
for (int i:v) vis[i]=0;
while (!v.empty()) rem(v.back()), v.pop_back();
for (int i=0;i<n;i++)
{
if (vis[i]) continue;
add(i), v.push_back(i);
if (get()==2) rem(i), v.pop_back();
}
if (v.size()<t) break;
}
return ans;
}
else
{
int l[n], r[n];
vector<int> mid[n];
for (int i=0;i<n;i++)
if (!se.count(i))
l[i]=-1, r[i]=v.size()-1, mid[(l[i]+r[i])/2].push_back(i);
for (int i=0;i<v.size();i++)
l[v[i]]=i-1,r[v[i]]=i;
for (int ct=0;ct<8;ct++)
{
bool it=0;
for (int i=0;i<n;i++)
if (l[i]+1<r[i]) it=1;
if (!it) break;
for (int i:v) rem(i);
for (int i=0;i<v.size();i++)
{
add(v[i]);
for (int x:mid[i])
{
add(x);
if (get()==2) r[x]=i;
else l[x]=i;
rem(x);
mid[(l[x]+r[x])/2].push_back(x);
}
}
}
map<int,int> cnt;
for (int i=0;i<n;i++)
cnt[r[i]]++;
int ans=n;
for (auto [i,x]:cnt) ans=min(ans,x);
return ans;
}
}
