#include "insects.h"
#include<bits/stdc++.h>

using namespace std;

typedef int ll;

random_device rd;
mt19937 rnd(rd());

ll min_cardinality(ll n) {
	vector<ll> fir, sec;
	for (ll i = 0; i < n; i++) {
		move_inside(i);
		if (press_button() == 2) {
			move_outside(i);
			sec.push_back(i);
		} else {
			fir.push_back(i);
		}
	}
	bool b = rnd() % 4 == 0;
	ll cr = fir.size();
	ll l = 1, r = n / cr + 1;
	while (r - l > 1) {
		ll mid = (l + r) / 2;
		vector<ll> nfir, nsec;
		vector<ll> nnfir;
		for (auto i : sec) {
			if (nfir.size() + fir.size() < mid * cr) {
				nnfir.push_back(i);
				continue;
			}
			move_inside(i);
			if (press_button() == mid + 1) {
				move_outside(i);
				nsec.push_back(i);
			} else {
				nfir.push_back(i);
			}
		}
		if (nfir.size() + fir.size() == mid * cr) {
			sec = nsec;
			for (auto i : nfir) {
				fir.push_back(i);
			}
			l = mid;
		} else {
			for (auto i : nfir) {
				move_outside(i);
			}
			sec = nfir;
			for (auto i : nnfir) {
				sec.push_back(i);
			}
			r = mid;
		}
		r = min(r, (ll)(fir.size() + sec.size()) / cr + 1);
	}
	return l;
}