#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
set<int> s;
void add(int i) {
assert(!s.count(i));
s.insert(i);
move_inside(i);
}
void del(int i) {
assert(s.count(i));
s.erase(i);
move_outside(i);
}
int get() {
return press_button();
}
int min_cardinality(int n) {
int cnt_distinct = 0;
for (int i = 0; i < n; i++) {
add(i);
if (get() == 1) {
cnt_distinct++;
} else {
move_outside(i);
}
}
while (!s.empty()) {
del(*s.begin());
}
int low = 1, high = n, sol = -1;
while (low <= high) {
int mid = (low + high) / 2;
while (!s.empty()) {
del(*s.begin());
}
for (int i = 0; i < n; i++) {
add(i);
if (get() > mid) {
del(i);
}
}
if ((int) s.size() == mid * cnt_distinct) {
sol = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
assert(sol != -1);
return sol;
}
