#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();
if (t == 1)
return n;
if (t == 2) {
int f = 1;
for (int i = 1; i < n; i++) {
move_inside(i);
int t = press_button();
if (t != f + 1)
move_outside(i);
else
f++;
}
return min(f, n - f);
}
int l = 1, r = n / t;
int ans = 1;
int k = t;
while (r - l > 0) {
int mid = (l + r) / 2;
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);
}
}
if (k < mid * t) {
r = maxP - 1;
for (int i: insects) {
if (getout[i]) {
move_outside(i);
getout[i] = false;
k--;
}
}
insects = remInsects;
} else {
l = mid + 1;
ans = mid;
insects = elimInsects;
}
}
return ans;
}
