#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng((long long) (new char));
vector<int> t;
set<int> s;
set<int> invalid;
void add(int i) {
assert(!s.count(i));
s.insert(i);
move_inside(t[i]);
}
void del(int i) {
assert(s.count(i));
s.erase(i);
move_outside(t[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) {
t.resize(n);
iota(t.begin(), t.end(), 0);
shuffle(t.begin(), t.end(), rng);
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 N;
{
int cnt_valid = 0;
for (int i = 0; i < n; i++) {
if (invalid.count(i)) continue;
cnt_valid++;
}
N = cnt_valid;
high = min(high, cnt_valid / cnt_distinct);
}
if (!(low <= high)) break;
int mid = low;
for (int i = low + 1; i <= high; i++) {
int fi = min(i * cnt_distinct, N - i * cnt_distinct);
int fmid = min(mid * cnt_distinct, N - mid * cnt_distinct);
if (fi > fmid) {
mid = i;
}
}
mid = (low + high) / 2;
vector<int> added_now, wait_now;
for (int i = 0; i < n; i++) {
if (invalid.count(i)) continue;
add(i);
if (get() > mid + sol) {
del(i);
wait_now.push_back(i);
} else {
added_now.push_back(i);
}
}
if (get_s_cardinality() == mid * cnt_distinct) {
for (auto &i : added_now) {
invalid.insert(i);
}
assert((int) added_now.size() >= mid * cnt_distinct);
int delta = mid;
low = mid + 1;
sol += delta;
low -= delta;
high -= delta;
} else {
for (auto &i : added_now) {
del(i);
}
for (auto &i : wait_now) {
invalid.insert(i);
}
assert((int) wait_now.size() >= N - mid * cnt_distinct);
high = mid - 1;
}
}
return sol;
}
