#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2020;
int n, in[maxn], qtd[maxn], block[maxn], blockout[maxn];
int ids[maxn];
int diff = 1;
int cnt = 0;
int cur = 1;
int check(int mid) {
for(int i = 0; i < n; i++) {
if(in[i] || block[i]) continue;
move_inside(i); in[i] = 1; cnt++;
int qry = press_button();
if(qry > cur) {
qtd[i] = qry;
}
cur = qry;
if(cur > mid) {
move_outside(i); in[i] = 0; cnt--;
cur--;
}
}
if(mid*diff == cnt) {
return true;
}
return false;
}
int min_cardinality(int N) {
n = N;
int qtdN = n;
// First count the number of different numbers
move_inside(0); in[0] = 1; cnt++;
qtd[0] = 1;
for(int i = 1; i < n; i++) {
move_inside(i); in[i] = 1; cnt++;
qtd[i] = 1;
diff++;
int qry = press_button();
blockout[i] = 1;
if(qry == 2) {
diff--;
move_outside(i); in[i] = 0; cnt--;
qtd[i] = 2;
blockout[i] = 0;
}
}
if(diff == 1) return n;
if(diff == n) return 1;
int l = 1;
int r = n/diff;
int ans = 1;
while(l <= r) {
int mid = max(l,(l+r)/2); // I want to see if the answer is <= mid
if(check(mid)) {
ans = mid;
l = mid+1;
// Everyone that is in will not be take off anymore
for(int i = 0; i < n; i++) {
if(in[i]) blockout[i] = 1;
}
}
else {
r = mid-1;
for(int i = 0; i < n; i++) {
if(!in[i]) {
block[i] = 1;
qtdN--;
}
if(in[i] && !blockout[i]) {
move_outside(i); in[i] = 0; cnt--;
}
}
cur = 0;
}
r = min(r,qtdN/diff);
}
return ans;
}
