#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
bool check(int N, int mid, int uniqueValues) {
int amountInside = 0;
// cout << "Mid: " << mid << '\n';
// cout << press_button() << '\n';
vector<int> trackInside;
for (int i = 0; i < N; i++) {
move_inside(i);
amountInside++;
trackInside.push_back(i);
int curr = press_button();
if (curr > mid) {
move_outside(i);
amountInside--;
trackInside.erase(trackInside.end() - 1);
}
else if (curr == mid && amountInside == (uniqueValues * mid)) {
for (auto &i: trackInside) {
move_outside(i);
}
return true;
}
}
for (auto &i: trackInside) {
move_outside(i);
}
return false;
}
int min_cardinality(int N) {
vector<int> mask(N, false);
int uniqueValues = 0;
for (int i = 0; i < N; i++) {
move_inside(i);
if (press_button() == 1) {
mask[i] = true;
uniqueValues++;
continue;
}
else {
move_outside(i);
}
}
for (int i = 0; i < N; i++) {
if (mask[i] == true) {
move_outside(i);
}
// cout << mask[i] << ' ';
}
// cout << check(N, 1024, uniqueValues) << '\n';
// cout << check(N, 511, uniqueValues) << '\n';
// cout << check(N, 255, uniqueValues) << '\n';
// cout << check(N, 127, uniqueValues) << '\n';
// cout << check(N, 63, uniqueValues) << '\n';
// cout << check(N, 31, uniqueValues) << '\n';
// cout << check(N, 15, uniqueValues) << '\n';
// cout << check(N, 7, uniqueValues) << '\n';
// cout << check(N, 3, uniqueValues) << '\n';
// cout << check(N, 1, uniqueValues) << '\n';
// cout << check(N, 2, uniqueValues) << '\n';
// return 0;
int high = 2048; // 2^11
int low = 0;
int ans = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
// cout << low << ' ' << high << ' ' << mid << '\n';
if (check(N, mid, uniqueValues)) {
// cout << "True" << '\n';
low = mid + 1;
ans = mid;
}
else {
// cout << "False" << '\n';
high = mid - 1;
}
}
return ans;
}
