#include"insects.h"
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define s(x) int(x.size())
using namespace std;
typedef vector<int> VI;
VI a,b,c;
mt19937 rnd(time(0));
int min_cardinality(int n){
	int m=0,r=1;
	rep(i,0,n){
		move_inside(i);
		if(press_button()>1)move_outside(i),a.pb(i);
		else ++m;
	}
	for(;s(a)>=m;){
		shuffle(a.begin(),a.end(),rnd);
		int l=(s(a)-1)/(2*m)+1;
		bool ok=0;
		for(int i:a){
			move_inside(i);
			if(ok||press_button()>r+l)move_outside(i),b.pb(i);
			else{
				c.pb(i);
				if(s(c)==l*m)ok=1;
			}
		}
		if(!ok){
			for(int i:c)move_outside(i);
			a=c;
		}else{
			r+=l,a=b;
		}
		b.clear(),c.clear();
	}
	return r;
}