#include "insects.h"

#include <bits/stdc++.h>

using namespace std;

int min_cardinality(int n) {
    vector<int> nw;
    for (int i = 0; i < n; ++i) {
        move_inside(i);
        nw.push_back(i);
    }
    mt19937 rnd(57);
    while (true) {
        shuffle(nw.begin(), nw.end(), rnd);
        vector<int> deleted;
        int mx_card = press_button();
        if (mx_card == (int)nw.size() || mx_card == 1) {
            return mx_card;
        }
        while (true) {
            move_outside(nw.back());
            deleted.push_back(nw.back());
            nw.pop_back();
            if (press_button() < mx_card) {
                break;
            }
        }
        vector<int> all_types;
        while (!deleted.empty()) {
            move_inside(deleted.back());
            if (press_button() == mx_card) {
                move_outside(deleted.back());
                all_types.push_back(deleted.back());
            } else {
                nw.push_back(deleted.back());
            }
            deleted.pop_back();
        }
        if (all_types.size() * mx_card == all_types.size() + nw.size()) {
            return mx_card;
        }
        for (auto insect : nw) {
            move_outside(insect);
        }
        for (auto insect : all_types) {
            move_inside(insect);
        }
        vector<int> nw2;
        while (!nw.empty()) {
            move_inside(nw.back());
            if (press_button() == 1) {
                nw2.push_back(nw.back());
                move_outside(nw.back());
            } else {
                move_outside(nw.back());
            }
            nw.pop_back();
        }
        nw = nw2;
    }
}