#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
const int mN = 5000;
bool diff[mN]={};
int r[mN]={};
int min_cardinality(int n) {
srand(time(0));
iota(r, r+n, 0);
// random_shuffle(r, r+n);
vector<int> diffs;
for (int i = 0; i < n; ++i) {
move_inside(r[i]);
diffs.push_back(r[i]);
int x = press_button();
if (x == 2) {
move_outside(r[i]);
diffs.pop_back();
}
}
int biggest_ans = n/diffs.size();
for (int i : diffs) move_outside(i), diff[i] = true;
vector<int> out;
vector<int> cur_in;
for (int i = 0; i < n; ++i) {
if (diff[r[i]]) continue;
out.push_back(r[i]);
}
int cursz = 0;
auto fill_gap = [&] (int newsz) {
vector<int> nout;
for (int i : out) {
move_inside(i);
cur_in.push_back(i);
if (press_button() >= newsz) {
nout.push_back(i);
move_outside(i);
cur_in.pop_back();
}
}
out.swap(nout);
cursz = newsz;
};
int low = 1, high = biggest_ans;
while (high != low) {
int mid = (high+low+1) >> 1;
if (mid < cursz) {
while (cur_in.size()) {
out.push_back(cur_in.back());
move_outside(cur_in.back());
cur_in.pop_back();
if (press_button() < mid) break;
}
cursz = mid-1;
}
fill_gap(mid);
vector<int> ndiffs;
for (int j : diffs) {
move_inside(j);
if (press_button() < mid) {
ndiffs.push_back(j);
}
move_outside(j);
}
if (ndiffs.size() == 0) low = mid;
else {
high = mid-1, ndiffs.swap(diffs);
out.clear();
}
}
return low;
}
/*
90
6 8 2 9 4 4 2 2 8 5 5 2 4 9 10 3 0 7 10 2 3 10 3 5 1 0 4 4 10 1 9 5 6 9 10 9 9 7 1 4 8 8 6 4 3 6 3 2 10 7 0 7 2 10 2 4 4 7 3 0 7 5 9 0 6 9 6 7 9 6 2 4 2 7 3 5 2 9 3 10 5 10 4 1 4 5 7 5 9 8
ans=4
*/
