#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> b;vector<bool> ind; int s, lr=INT_MAX;
int min_cardinality(int n) {
vector<int> f; vector<bool> u1(n, false), indx(n, false);
bool p=false;
for(int i=0; i<n; i++)
{
if(!u1[i])
{
for(int j=0; j<n; j++){if(indx[j]){move_outside(j); indx[j]=false;}}
f.clear(); ind.assign(n, false); move_inside(i); indx[i]=true; s=press_button();
f.push_back(i); u1[i]=true; ind[i]=true; vector<char> tr(n, 0);
while(true)
{
for(int j=0; j<n; j++){if(indx[j]&&!ind[j]){move_outside(j); indx[j]=false;}} b.clear(); int t=0;
for(int j=0; j<n&&t<s; j++){if(!u1[j]&&!indx[j]&&!tr[j]) {b.push_back(j); move_inside(j); indx[j]=true; t++;}}
if(b.empty()){lr=min(lr, s); break;} int y=press_button();
if(s==y)
{
for(auto x:b){ tr[x]=1; move_outside(x); indx[x]=false;}
b.clear(); continue;
}
while(b.size()>1)
{
vector<int> h1, h2;
for(int j=0; j<b.size()/2; j++){ h1.push_back(b[j]);}
for(int j=b.size()/2; j<b.size(); j++){h2.push_back(b[j]); move_outside(b[j]); indx[b[j]]=false;}
if(press_button()<=s)
{
for(auto x: h1){if(indx[x]){move_outside(x); indx[x]=false;}} b.clear();
for(auto x:h2){b.push_back(x); move_inside(x); indx[x]=true;}
}
else
{
b.clear();for(auto x:h1){b.push_back(x);}
}
}
f.push_back(b[0]); ind[b[0]]=true; u1[b[0]]=true; s++;
lr=min(lr, s);
for(int j=0; j<n; j++){if(indx[j]&&!ind[j]){move_outside(j); indx[j]=false;}}
}
}
}
return lr;
}
