#include <bits/stdc++.h>
#include "insects.h"
// #include "stub.cpp"
using namespace std;
const int MXN = 2005;
int sz;
bool a[MXN], dead[MXN], alive[MXN];
bool add(int i){
if (a[i] or dead[i]) return 0;
sz++;
a[i] = 1;
move_inside(i);
return 1;
}
bool rem(int i){
if (!a[i] or alive[i]) return 0;
sz--;
a[i] = 0;
move_outside(i);
return 1;
}
int get(){
return press_button();
}
int min_cardinality(int n){
int d = 0;
for (int i = 0; i < n; i ++){
add(i);
if (get() == 2)
rem(i);
d += a[i];
if (a[i]) alive[i] = 1;
}
if (d == 1) return n;
int l = 1, r = n / d + 1;
vector<int> kil, pro;
while (r - l > 1){
int mid = (l + r) / 2;
for (int i = 0; i < n; i ++)
rem(i);
int last = l;
for (int i = 0; i < n; i ++){
if (!add(i)) continue;
int val = get();
if (val > mid or (last < mid and val == mid))
kil.push_back(i);
if (val <= mid)
pro.push_back(i);
if (val > mid)
rem(i);
else last = val;
}
if (sz == d * mid){
kil.clear();
for (int i : pro)
alive[i] = 1;
pro.clear();
l = mid;
}
else{
pro.clear();
for (int i : kil)
dead[i] = 1;
kil.clear();
r = mid;
}
}
return l;
}
