#include "insects.h"
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 1000005
#define inf 0x3f3f3f3f

int n,siz; 
vi in,out;
int cnt;

vector<bool>now,lst;
void move_in(int i){now[i]=1;}
void move_out(int i){now[i]=0;}
map<vector<bool>,int>mp;
int query(){
	if(mp.count(now))return mp[now];
	For(i,0,n-1){
		if(now[i]&&!lst[i])move_inside(i);
		if(!now[i]&&lst[i])move_outside(i);
		now[i]=lst[i];
	}
	return mp[now]=press_button();
}

bool chk(int x)
{
	vi tin,tout; int c=0;
	for(auto u:out){
		if(tin.size()==x*siz){tout.pb(u);continue;}
		move_in(u);
		++c;
		if(c<=x||query()<=x+cnt)tin.pb(u);
		else tout.pb(u),move_out(u);
	}
	if(tin.size()==x*siz){
		out=tout;
		cnt+=x; return 1;
	}else{
		for(auto u:tin) move_out(u);
		out=tin; return 0;
	}
}
int min_cardinality(int nn)
{
	n=nn;
	now.resize(n),lst=now;
	For(i,0,n-1){
		move_in(i);
		if(query()==1)in.pb(i);
		else out.pb(i),move_out(i);
	}
	if(in.size()==n)return 1;
	int l=2,r=n/in.size(),res=1; cnt=1; siz=in.size();
	while(l<=r){
		int mid=(l+r+1)/2;
		if(chk(mid-l+1))l=mid+1,res=mid;
		else r=mid-1;
	}return res;
}