#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
set<int> s;
set<int> invalid;
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 get_s_cardinality() {
int sol = 0;
for (auto &x : s) {
if (!invalid.count(x)) {
sol++;
}
}
return sol;
}
int min_cardinality(int n) {
int cnt_distinct = 0;
for (int i = 0; i < n; i++) {
add(i);
if (get() == 1) {
cnt_distinct++;
} else {
del(i);
}
}
for (auto &i : s) {
invalid.insert(i);
}
int low = 1, high = n, sol = 1;
while (low <= high) {
assert(low >= 1);
/**{
int cnt_valid = 0;
for (int i = 0; i < n; i++) {
if (invalid.count(i)) continue;
cnt_valid++;
}
high = min(high, cnt_valid / cnt_distinct);
}**/
if (!(low <= high)) break;
int mid = (low + high) / 2;
mid = 1;
vector<int> added_now;
for (int i = 0; i < n; i++) {
if (invalid.count(i)) continue;
add(i);
if (get() > mid + sol) {
del(i);
} else {
added_now.push_back(i);
}
}
if (get_s_cardinality() == mid * cnt_distinct) {
for (auto &i : added_now) {
invalid.insert(i);
}
int delta = mid;
low = mid + 1;
sol += delta;
low -= delta;
high -= delta;
} else {
for (auto &i : added_now) {
s.erase(i);
}
high = mid - 1;
}
}
return sol;
}
