#include "insects.h"

#include <bits/stdc++.h>

using namespace std;

int min_cardinality(int n) {
    set<int> nw;
    for (int i = 0; i < n; ++i) {
        move_inside(i);
        nw.insert(i);
        if (press_button() != 1) {
            move_outside(i);
            nw.erase(i);
        }
    }
    int cnt_of_types = nw.size();
    if (cnt_of_types == 1) {
        return n;
    }
    int l = 1, r = n;
    while (l < r - 1) {
        int m = (l + r) / 2;
        vector<int> added;
        for (int i = 0; i < n; ++i) {
            if (!nw.count(i)) {
                move_inside(i);
                nw.insert(i);
                if (press_button() > m) {
                    move_outside(i);
                    nw.erase(i);
                } else {
                    added.push_back(i);
                }
            }
        }
        if (nw.size() != cnt_of_types * m) {
            int diff = cnt_of_types * m - (int)nw.size();
            r = m - diff / (cnt_of_types - 1);
            for (auto insect : added) {
                move_outside(insect);
                nw.erase(insect);
            }
        } else {
            l = m;
        }
    }
    return l;
}