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

using namespace std;

namespace {

int n;

}

int min_cardinality(int grdn) {
	n = grdn;
	vector<int> diff;
	for (int i = 0; i < n; ++i) {
		move_inside(i);
		if (press_button() == 2) {
			move_outside(i);
		} else {
			diff.push_back(i);
		}
	}
	for (int i : diff) {
		move_outside(i);
	}
	vector<int> kek;
	for (int i = 0; i < n; ++i) {
		kek.push_back(i);
	}
	int ret = 0;
	int l = 1, r = n + 1;
	while (r - l > 1 && !kek.empty())  {
		int mid = (l + r) / 2;
		vector<int> cur;
		for (int i : kek) {
			move_inside(i);
			if (press_button() > mid) {
				move_outside(i);
			} else {
				cur.push_back(i);
			}
		}
		if ((int)cur.size() == (int)diff.size() * mid) {
			vector<int> kek1;
			for (int i : kek) {
				if (!binary_search(cur.begin(), cur.end(), i)) {
					kek1.push_back(i);
				}
			}
			ret += mid;
			kek = kek1;
			if (kek.empty()) {
				break;
			}
			l = mid + 1;
			l -= mid;
			r -= mid;
		} else {
			r = mid;
		}
		for (int i : cur) {
			move_outside(i);
		}
	}
	if (!kek.empty()) {
		ret += l;
	}
	return l;
}