#include "insects.h"
#include "bits/stdc++.h"
using namespace std;
int min_cardinality(int N) {
int distinct = 0;
vector<bool> inserted(N);
for (int i = 0; i < N; ++i) {
move_inside(i);
int most_freq = press_button();
if (most_freq > 1) {
move_outside(i);
} else {
inserted[i] = true;
distinct++;
}
}
vector<bool> bad(N);
int l = 1, r = N / distinct;
while (l < r) {
int mid = (l + r + 1) / 2;
for (int i = 0; i < N; ++i) {
if (bad[i]) {
continue;
}
move_inside(i);
int most_freq = press_button();
if (most_freq > mid) {
move_outside(i);
} else {
move_inside(i);
inserted[i] = true;
}
}
int cnt = accumulate(inserted.begin(), inserted.end(), 0);
if (cnt == distinct * mid) {//inserted indices must not be removed under any condition
l = mid;
for (int i = 0; i < N; ++i) {
if (inserted[i]) {
bad[i] = true;
}
}
} else {//non-inserted indices must not be inserted under any condition
r = mid - 1;
for (int i = 0; i < N; ++i) {
if (!inserted[i]) {
bad[i] = true;
} else if (!bad[i]) {
inserted[i] = false;
move_outside(i);
}
}
}
}
return l;
}
