#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2020;
int n, in[maxn], qtd[maxn];
int diff = 1;
int cnt = 0;
int cur = 1;
int check(int mid) {
for(int i = 0; i < n; i++) {
if(in[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;
}
else {
return false;
}
}
int min_cardinality(int N) {
n = 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();
if(qry == 2) {
diff--;
move_outside(i); in[i] = 0; cnt--;
qtd[i] = 2;
}
}
if(diff == 1) return n;
if(diff == n) return 1;
int l = 1;
int r = n;
int ans = -1;
while(l <= r) {
int mid = (l+r)/2; // I want to see if the answer is <= mid
if(check(mid)) {
ans = mid;
l = mid+1;
}
else {
r = mid-1;
}
for(int i = 0; i < n; i++) {
if(in[i]) {
move_outside(i); in[i] = 0; cnt--;
}
}
cur = 0;
}
return ans;
}
