#include "insects.h"
#include <bits/stdc++.h>
#ifdef GUDEB
#define D(x) cerr << #x << ": " << (x) << '\n';
#define ifdeb if(true)
#else
#define D(x) ;
#define ifdeb if(false)
#endif
#define all(x) begin(x), end(x)
using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;
int min_cardinality(int n) {
vector<bool> skip(n);
vector<bool> box(n);
int s = 0;
for(int i = 0; i < n; ++i) {
box[i] = true;
move_inside(i);
++s;
int c = press_button();
if(c > 1) {
move_outside(i);
--s;
box[i] = false;
}
}
D(s)
if(s == n) return 1;
for(int i = 0; i < n; ++i) {
if(box[i]) {
move_outside(i);
skip[i] = true;
}
}
int rm = 1;
int f = 1;
int t = n/s;
while(f != t) {
int m = (f+t+1)/2;
D(f)
D(t)
D(m)
int ss = 0;
for(int i = 0; i < n; ++i) {
if(skip[i]) continue;
box[i] = true;
++ss;
move_inside(i);
int c = press_button();
if(c > m-rm) {
move_outside(i);
box[i] = false;
--ss;
}
}
D(ss)
if(ss == s*(m-rm)) {
rm = m;
f = m;
for(int i = 0; i < n; ++i) {
if(box[i]) skip[i] = true;
}
} else {
t = m-1;
for(int i = 0; i < n; ++i) {
if(!box[i]) skip[i] = true;
}
}
for(int i = 0; i < n; ++i) {
if(box[i]) move_outside(i);
box[i] = false;
}
}
return f;
}
