#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int m, op=0, c=0, pk=0;
bool f1(int n)
{
for(int i=0; i<n; i++){move_outside(i);} int lk=0, pl=-1; vector<char>ind(n, 0);
for(int i=0; i<m; i++)
{
if(press_button()!=0){for(int j=0; j<n; j++) move_outside(j);}
int uj=press_button(), ok=0; vector<int> y1; y1.reserve(n);
for(int j=0; j<n; j++)
{
if(ind[j]) continue; move_inside(j); int no=press_button();
if(no==uj)move_outside(j); else{uj=no; ind[j]=1; lk++; ok++; y1.push_back(j);if(lk==n) return true;}
}
if(i==0)
{
pl=ok; if(pl==0) return (n==0);
if(1LL*m*pl<n)
{
for(auto x:y1) move_outside(x); if(press_button()!=0){for(int j=0; j<n; j++) move_outside(j);}
return false;
}
}
for(auto x:y1) move_outside(x); if(press_button()!=0){for(int j=0; j<n; j++) move_outside(j);}
if(ok==0) break;
}
return (lk==n);
}
int min_cardinality(int n) {
int l=1, r=n, q=n;
while (l<=r)
{
m = (l+r)/2;if (f1(n)){ r=m-1;q=m;} else l=m+1;
}
return q;
}
