#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
template <class F, class S>
bool chmin(F &u, const S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
int min_cardinality(int n) {
vector <int> p;
for ( int i = 0; i < n; i++ ){
move_inside(i);
if ( press_button() == 1 ){
p.pb(i);
} else{
move_outside(i);
}
}
int k = (int)p.size();
if ( __lg(n / k + 1) >= k ){
vector <int> us(n);
for ( auto &j: p ){
move_outside(j);
} p.clear();
vector <int> f;
while ( !*min_element(all(us)) ){
int cnt = 0;
for ( int i = 0; i < n; i++ ){
if ( us[i] ) continue;
move_inside(i);
if ( press_button() == cnt + 1 ){
cnt += 1; p.pb(i);
} else{
move_outside(i);
}
}
f.pb(cnt);
for ( auto &x: p ){
us[x] = 1;
move_outside(x);
} p.clear();
}
return *min_element(all(f));
}
for ( auto &x: p ){
move_outside(x);
} p.clear();
auto ok = [&](int m){
int cnt = 0;
for ( int i = 0; i < n; i++ ){
move_inside(i);
if ( press_button() > m ){
move_outside(i);
} else{
p.pb(i);
cnt += 1;
}
}
for ( auto &x: p ){
move_outside(x);
} p.clear();
return cnt == k * m;
};
int l = 1, r = n / k + 1;
while ( l + 1 < r ){
int m = (l + r) / 2;
if ( ok(m) ) l = m;
else r = m;
}
return l;
}
