#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
namespace{
bool taken[2000 + 5];
void add(int i, vector<int> &v){
taken[i] = true;
v.push_back(i);
move_inside(i);
}
void undo(vector<int> &v){
taken[v.back()] = false;
move_outside(v.back());
v.pop_back();
}
int query(){
return press_button();
}
}
int min_cardinality(int N) {
for(int i = 0; i < N; i++) taken[i] = false;
vector<int> v;
for(int i = 0; i < N; i++){
add(i,v);
if(query() > 1) undo(v);
}
int s = 1;
int e = N/v.size();
while(s < e){
long long int m = (s + e+1)/2;
vector<int> v1;
vector<int> v2;
for(int i = 0; i < N; i++){
if(!taken[i]){
add(i,v1);
if(query() > m){
undo(v1);
v2.push_back(i);
}
}
}
if(v1.size() == v.size() * (m-s)){
s = m;
}
else{
e = s + v1.size() / v.size();
for(int i : v2) taken[i] = true;
while(!v1.empty()){
undo(v1);
}
}
}
return s;
}
