#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> ord;
int vis[2000], act = 0;
void get_in(int u) {
u = ord[u];
if(vis[u]) return ;
act++;
vis[u] = 1;
move_inside(u);
}
void get_out(int u) {
u = ord[u];
if(!vis[u]) return ;
act--;
vis[u] = 0;
move_outside(u);
}
int min_cardinality(int n) {
ord = vector<int>(n);
for(int i=1; i<n; i++) ord[i] = i;
shuffle(ord.begin(), ord.end(), rng);
int l=2, r=n, ans=1;
get_in(0);
for(int i=1; i<n; i++) {
get_in(i);
if(press_button() == 2) get_out(i);
}
int D = act;
r = n / D;
while(l <= r) {
int mid = (l + r) / 2;
vector<int> now;
for(int i=0; i<n; i++) {
if(act == mid * D) break;
if(vis[i]) continue;
get_in(i);
if(press_button() == mid + 1) {
get_out(i);
continue;
}
now.push_back(i);
}
if(act == mid * D) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
for(int u : now) get_out(u);
}
}
return ans;
}
