#include <bits/stdc++.h>
#include "insects.h"
const int N = 1e5;
using namespace std;
mt19937 rand1(time(0));


int cnt, opt[N + 5], vis[N + 5],vs1[N + 5];
int query() {return press_button();}

int min_cardinality(int n) {
	int now = 0;
	for(int i = 1; i <= n; ++i) {
		move_inside(i - 1);
		if (query() > 1) move_outside(i - 1);
		else ++cnt, vis[i] = 1, ++now;
	}
	if (cnt == 1) return n;
	int l = 1, r = n / cnt, mid, ans;
	while(l <= r) {
		int mid = l + r >> 1;
		for(int i = 1; i <= n; ++i) opt[i] = i, vs1[i] = 0;
		shuffle(opt + 1, opt + n + 1, rand1);
		for(int i = 1; i <= n; ++i)
			if (!vis[opt[i]]){
				if (cnt * mid <= now) break;
				move_inside(opt[i] - 1); ++now;
				if (query() > mid) move_outside(opt[i] - 1), --now;
				else vs1[opt[i]] = 1;
			}
		if (now < cnt * mid) {
			r = mid - 1;
			for(int i = 1; i <= n; ++i)
				if (vs1[i]) move_outside(i - 1), --now;
				else vis[i] = 1;
		}
		else  {
			l = mid + 1, ans = mid;;
			for(int i = 1; i <= n; ++i)
				if (vs1[i]) vis[i] = 1;
		}

	}
	return ans;
}