#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
int min_cardinality(int N) {
set<ll> cnums;
for (ll i=0;i<N;i++) {
cnums.insert(i);
}
vector<ll> currin;
for (ll x: cnums) {
move_inside(x);
if (press_button()>1) {
move_outside(x);
} else {
currin.push_back(x);
}
}
ll nterms = currin.size();
for (ll x: currin) {
move_outside(x);
}
while (1) {
ll qn = cnums.size()/nterms;
vector<ll> vdisc; //discard
vector<ll> vin;
for (ll x: cnums) {
move_inside(x);
if (press_button()>=qn) {
move_outside(x);
vdisc.push_back(x);
} else {
vin.push_back(x);
}
}
for (ll x: vin) {
move_outside(x);
}
set<ll> nnums;
ll NDEL = 0;
for (ll y: vdisc) {
move_inside(y);
if (press_button()>1) {
move_outside(y);
} else {
NDEL++;
}
}
for (ll y: vin) {
move_inside(y);
if (press_button()==1) {
nnums.insert(y);
}
move_outside(y);
}
nterms -= NDEL;
if (nterms == 0) {
return qn;
}
cnums = nnums;
}
}
