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

using namespace std;
using ll = long long;

mt19937 rnd(228);

int min_cardinality(int N) {
    vector<int> a(N);
    iota(a.begin(), a.end(), 0);
    shuffle(a.begin(), a.end(), rnd);

    vector<int> leaders, inside(N);
    int maxSize = 0, T = 0, cntIn = 0, lastQueryT = 0;
    int queriesCnt[3]{};

    auto insert = [&](int x) -> bool {
        if (inside[x]) {
            return false;
        }
        cntIn += 1;
        move_inside(x);
        T += 1;
        queriesCnt[0] += 1;
        return inside[x] = true;
    };

    auto erase = [&](int x) -> void {
        if (!inside[x]) {
            return;
        }
        cntIn -= 1;
        move_outside(x);
        T += 1;
        queriesCnt[1] += 1;
        inside[x] = false;
    };

    auto query = [&]() -> int {
        if (T == lastQueryT) {
            return maxSize;
        }
        lastQueryT = T;
        queriesCnt[2] += 1;
        return maxSize = press_button();
    };

    vector<int> others;

    for (int x : a) {
        insert(x);
        if (query() == 1) {
            leaders.push_back(x);
        } else {
            others.push_back(x);
            erase(x);
        }
    };


    int ans = N;

    if (size(leaders) > size(others)) {
        return 1;
    } else if (size(leaders) == 1) {
        return N;
    }

    int lo = 1, hi = 2 + size(others) / size(leaders);
    
    while (lo + 1 < hi) {
        int mid = lo + hi >> 1;
        vector<int> in, out;
        for (int x : others) {
            if (insert(x) && query() > mid) {
                erase(x);
            } else if (query() * size(leaders) == cntIn) {
                break;
            }
        }
        for (int x : others) {
            if (inside[x]) {
                in.push_back(x);
            } else {
                out.push_back(x);
            }
        }
        if (query() * size(leaders) == cntIn) {
            lo = mid;
            others = move(out);
        } else {
            hi = mid;
            others = move(in);
            for (int x : others) {
                erase(x);
            }
        }
    }

    return lo;
}