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


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

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