#include "insects.h"
#include <bits/stdc++.h>
#define pb push_back
#define md ((l+r+1)>>1)
#define ins move_inside
#define out move_outside
#define press press_button
using namespace std;
const int MAXN = 2010;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, dif;
int arr[MAXN];
bool ada[MAXN], les[MAXN], tag[MAXN];
int cnt = 1;
bool ri = 0;
bool cek(int x){
vector<int> vec;
for(int i=0; i<n; i++){
if(ada[i] || tag[i]) continue;
ins(arr[i]);
if(press() == x+1){
out(arr[i]);
vec.pb(i);
} else {
ada[i] = 1;
}
}
int tot = 0;
for(int i=0; i<n; i++) tot += ada[i];
if(dif * x == tot){
for(int i=0; i<n; i++)
les[i] = ada[i];
return 1;
}
for(int i=0; i<n; i++){
if(ada[i]==1 && les[i]==0){
out(arr[i]); ada[i] = 0;
}
}
for(auto in : vec) tag[in] = 1;
return 0;
}
int min_cardinality(int N) {
n = N;
vector<int>V;
for(int i=0; i<n; i++) V.pb(i);
shuffle(V.begin(), V.end(), rng);
for(int i=0; i<n; i++) arr[i] = V[i];
int las;
for(int i=0; i<n; i++){
ins(arr[i]);
if(press() != 1) out(arr[i]); // keluarin
else {
dif++; ada[i] = 1;
}
}
for(int i=0; i<n; i++)
les[i] = ada[i];
int l=2, r=n/dif, mid=0;
while(l<=r){
mid = md;
if(cek(mid)){
cnt = mid; l = mid+1;
} else {
r = mid-1;
}
}
return cnt;
}
