#include "insects.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
int d;
int min_cardinality(int n) {
vector <int> act;
bool used[n + 1];
fill(used, used + n + 1, false);
for(int i = 0; i < n; i++){
move_inside(i);
int x = press_button();
if(x == 2) move_outside(i);
else act.pb(i);
}
//for(int to : act) cout << to << ' ';
//int l = 0, r = act.size();
for(int to : act) move_outside(to);
int d = act.size();
int l = 1, r = n / d + 1;
vector <int> cur;
while(l + 1 < r){
int mid = (l + r) / 2;
vector <int> vv;
for(int i = 0; i < n; i++){
if(used[i]) continue;
move_inside(i);
int x = press_button();
if(x > mid) move_outside(i);
else vv.pb(i);
}
int x = cur.size() + vv.size();
if(x == mid * d){
l = mid;
for(int to : vv) used[to] = true, cur.pb(to);
}
else{
r = mid;
for(int i = 0; i < n; i++) used[i] =true;
for(int to : vv) used[to] = false, move_outside(to);
}
}
return l;
}
