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

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, u;
vector<int> p;
set<int> cur, lef;
void add(int i) {
    cur.insert(i);
    move_inside(i);
}
void del(int i) {
    if(cur.count(i)) {
        cur.erase(i);
        move_outside(i);
    }
}
int l , r;
bool check(int mid) {
    if(mid * u > n) return false;
    int col = 0;
    int val = (int)lef.size() + (int)cur.size();
    set<int> nf = lef;
    for(int i : lef) {
        add(i); 
        if(col <= val - mid * u && press_button() > mid) {
            del(i);
            nf.erase(i);
            col++;
        }
        if(col > val - mid * u) break;
    }
    if(col == val - mid * u) {
        set<int> nv;
        for(int i : lef) {
            if(!cur.count(i)) { 
                nv.insert(i);
            }
        }
        lef.swap(nv);
        return 1;   
    }
    set<int> nv;
    for(int i : lef) {
        if(cur.count(i)) {
            nv.insert(i);
        }
        del(i);
    }
    lef.swap(nf);
    return false;
}
int min_cardinality(int NN) {
    n = NN;
    for(int i = 0; i < n; i++) {
        lef.insert(i);
    }
    int col = 0;
    for(int i = 0; i < n; i++) {    
        add(i);
        if(press_button() == 2) {
            del(i);
            col++;
        } else {
            lef.erase(i);
        }
    }
    u = (int)cur.size();
    if(u == 1) {
        return n;
    }
    l = 1, r = n / u;
    int res;
    while(r - l > 0) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            l = mid+1;
            res = mid;
        } else {
            r = mid-1;
        }
    }
    return res;
}