#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int inside[2005], kys[2005];
void in(ll x){
inside[x] = 1;
move_inside(x);
}
void out(ll x){
inside[x] = 0;
move_outside(x);
}
ll count(){
ll cnt = 0;
for (int i=0;i<2005;i++){
if (inside[i]) cnt++;
}
return cnt;
}
vector<ll> added;
ll check(ll m, int n, ll prev){
if (prev < m){
added.clear();
for (int i=0;i<n;i++){
if (inside[i] || kys[i]) continue;
in(i);
if (press_button() > m) out(i);
else added.push_back(i);
}
}
else{
vector<ll> arr;
for (int i:added){
if (!inside[i]) continue;
out(i);
arr.push_back(i);
}
added.clear();
for (int i=0;i<arr.size();i++){
in(arr[i]);
if (press_button() > m) out(arr[i]);
else added.push_back(arr[i]);
}
arr.clear();
}
return count();
}
int min_cardinality(int n) {
in(0);
added.push_back(0);
for (int i=1;i<n;i++){
in(i);
if (press_button() > 1) out(i);
else added.push_back(i);
}
ll group = count();
ll l = 1, r = n/group;
ll checked[r+1];
memset(checked,-1,sizeof(checked));
checked[1] = 1;
ll prev = 1;
while (l<r){
ll m = (l+r)>>1;
if (checked[m] == -1){
ll cnt = check(m, n, prev);
prev = m;
checked[m] = cnt;
}
if (group*m == checked[m]) l = m+1;
else {
r = m;
for (int i=0;i<n;i++){
if (!inside[i]) kys[i] = 1;
}
}
}
return l-1;
}
