#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e3;
int n;
bool getout[MAX_N];
vector<int> distinct, insects;
mt19937 rnd(100111);
int min_cardinality(int N) {
n = N;
move_inside(0);
distinct.push_back(0);
for (int i = 1; i < n; i++) {
move_inside(i);
if (press_button() == 2) {
move_outside(i);
insects.push_back(i);
}
else
distinct.push_back(i);
}
int t = distinct.size();
int l = 1, r = n / t + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
int delta = rnd() % (r - l) - (r - l) / 2;
if (delta + mid < r && mid + delta > l)
mid += delta;
int k = l * t;
int maxP = 0;
shuffle(insects.begin(), insects.end(), rnd);
vector<int> remInsects, elimInsects;
for (int i: insects) {
move_inside(i);
getout[i] = true;
int p = press_button();
if (p > mid) {
move_outside(i);
elimInsects.push_back(i);
}
else {
k++;
maxP = max(maxP, p);
remInsects.push_back(i);
}
}
// printf("%d %d\n", mid, k);
if (k < mid * t) {
r = maxP;
for (int i: insects) {
if (getout[i])
move_outside(i);
getout[i] = false;
} insects = remInsects;
}
else {
l = mid;
insects = elimInsects;
}
}
return l;
}
