#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();
    int it = 0;
    for(int i : lef) {
        add(i); 
        if(press_button() > mid) {
            del(i);
            col++;
        }
        it++;
    }
    if(col == val - mid * u) {
        set<int> nv;
        for(int i : lef) {
            if(!cur.count(i)) { 
                nv.insert(i);
            }
        }
        lef.swap(nv);
        return 1;
    }
    // l = max(l, mid - (col - val + mid * u));
    set<int> nv;
    for(int i : lef) {
        if(cur.count(i)) {
            nv.insert(i);
        }
        del(i);
    }
    lef.swap(nv);
    return false;
}
int min_cardinality(int NN) {
    n = NN;
    for(int i = 0; i < n; i++) {
        lef.insert(i);
    }
    for(int i = 0; i < n; i++) {
        add(i);
        if(press_button() == 2) {
            del(i);
        } else {
            lef.erase(i);
        }
    }
    u = (int)cur.size();
    if(u <= 3) {
        vector<int> e,c(u,0);
        for(int i:cur)e.push_back(i);
        for(int i:e) del(i);
        for(int i:lef){
            add(i);
            for(int j=0;j<u;j++){
                add(e[j]);
                if(press_button()==2){
                    c[j]++;
                    del(e[j]);
                    break;
                }
                del(e[j]);
            }
            del(i);
        }
        int mx=n;
        for(int j=0;j<u;j++){
            mx=min(mx,c[j]+1);
        }
        return mx;
    }
    l = 1, r = n + 1;
    // l + (r - l) / 3
    while(r - l > 1) {
        int mid = (l * 2 + r) / 3;
        if(r - l < 4) {
            mid = (l + r) >> 1;
        } else if(rng()% 3 == 0) {
            mid = (l + r) >> 1;
        } else if(rng()%4 == 0) {
            mid = (2 * r + l) /3;
        }
        if(check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return l;
}