#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2000;
bool isIn[MAX_N], nxt[MAX_N];
map<vector<int>, int> his;
int ask(const vector<int> &a) {
// if (his.count(a)) {
// return his[a];
// }
for (int i = 0; i < MAX_N; ++i) {
nxt[i] = 0;
}
for (auto x : a) {
nxt[x] = 1;
}
for (int i = 0; i < MAX_N; ++i) {
if (isIn[i] > nxt[i]) {
move_outside(i);
}
if (isIn[i] < nxt[i]) {
move_inside(i);
}
isIn[i] = nxt[i];
}
//return his[a] = press_button();
return press_button();
}
int min_cardinality(int n) {
vector<int> a(n);
iota(a.begin(), a.end(), 0);
vector<int> nxt, inside;
for (auto x : a) {
inside.push_back(x);
if (ask(inside) > 1) {
inside.pop_back();
nxt.push_back(x);
}
}
int numDistinct = inside.size();
int res = 1;
a = nxt;
srand(123);
int l = 1, r = (int) a.size() / numDistinct;
while (l <= r) {
int mid = (l + r + rand() % 2) >> 1;
vector<int> outside;
inside.clear();
for (auto x : a) {
inside.push_back(x);
// if ((int)inside.size() <= mid) {
// continue;
// }
if (ask(inside) > mid) {
inside.pop_back();
outside.push_back(x);
}
}
if ((int)inside.size() == numDistinct * mid) {
res += mid;
a = outside;
l = 1;
r = (int)a.size() / numDistinct;
//allIn = false;
//cerr << "to r" << endl;
} else {
a = inside;
l = max(1, (int)a.size() - mid * (numDistinct - 1));
r = (int)a.size() / numDistinct;
//allIn = true;
//cerr << "to l" << endl;
}
}
return res;
}
