#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
mt19937 Rnd(time(0)); 

int k, cnt, a[N];
bool vs[N], inmid[N];

inline void ins(int x) { ++cnt; move_inside(x - 1); }
inline void del(int x) { --cnt; move_outside(x - 1); }
int min_cardinality(int n) {
    for (int i = 1; i <= n; ++i) {
        ins(i);
        if (press_button() > 1) del(i);
        else vs[i] = 1, ++k; 
    }
    if (k == 1) return n; 
    int l = 1, r = n / k + 1;
    while (l + 1 != r) {
        int mid = l + r >> 1; 
        for (int i = 1; i <= n; ++i)
            inmid[i] = 0, a[i] = i;
        shuffle(a + 1, a + n + 1, Rnd);
        for (int i = 1; i <= n; ++i) if (!vs[a[i]]) {
            if (k * mid == cnt) break;
            ins(a[i]); 
            if (press_button() > mid) del(a[i]); 
            else inmid[a[i]] = 1; 
        }

        if (k * mid == cnt) {
            l = mid; 
            for (int i = 1; i <= n; ++i)
                if (inmid[i]) vs[i] = 1; 
        } else {
            r = max(l + 1, min(mid, cnt / k + 1)); 
            for (int i = 1; i <= n; ++i)
                if (inmid[i]) del(i); 
                else vs[i] = 1; 
        }
    }
    return l; 
}