#pragma GCC optimize("O3")
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
//g++ -std=c++17 insects.cpp stub.cpp
int D, N;
const int MAX = 3000;
int mark[MAX], inside[MAX];
vector<int> p;
int cnt = 0;
bool check(int m){
for(auto i : p){
if(cnt == m * D) break;
if(mark[i]) continue;
move_inside(i);
if(press_button() > m){
move_outside(i);
}else{
cnt++;
inside[i] = 1;
}
}
if(cnt == m * D){
for(int i = 0; i < N; i++) if(inside[i]) mark[i] = 1;
return false;
}
for(int i = 0; i < N; i++){
if(!inside[i]) mark[i] = 1;
else if(!mark[i]){
move_outside(i);
inside[i] = 0;
cnt--;
}
}
return true;
}
int min_cardinality(int n) {
N = n;
p.resize(N);
for(int i = 0; i < N; i++) p[i] = i;
random_shuffle(p.begin(), p.end());
for(int i = 0; i < N; i++){
move_inside(i);
if(press_button() > 1){
move_outside(i);
}else{
cnt++;
inside[i] = 1;
mark[i] = 1;
}
}
D = cnt;
int l = 1, r = N / D;
while(l <= r){
int m = (l + r) / 2;
if(check(m)) r = m - 1;
else l = m + 1;
}
return r;
}
