#include "insects.h"
#include <vector>
#include <bits/stdc++.h>
#define rep(a,b,c) for(ll a=b; a<c; a++)
#define repr(a,b,c) for(ll a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define mid ((l+r)>>1)
#define ppb pop_back
using namespace std;
using vi = vector<int>;
int min_cardinality(int n) {
vi a, b, c, d;
rep(i,0,n){
move_inside(i);
a.pb(i);
if(press_button()==2){
move_outside(i);
a.ppb();
b.pb(i);
}
}
int l=1, r=n/a.size(), x;
repa(e,a) move_outside(e);
while(l<=r){
repa(e,b){
move_inside(e);
c.pb(e);
if(press_button()==mid){
move_outside(e);
c.ppb();
d.pb(e);
}
}
x=mid;
repa(e,a){
move_inside(e);
x=min(x,press_button());
move_outside(e);
}
repa(e,c) move_outside(e);
if(x==mid){
l=mid+1;
b=d;
c.clear();
d.clear();
}else{
r=mid-1;
b=c;
c.clear();
d.clear();
}
}
return r;
}
