#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int N = 2e3+3, inf = INT_MAX;
mt19937 rng((time(nullptr)) + (chrono::steady_clock::now().time_since_epoch().count()) + ((uint64_t) new char));
int n, m, ans;
vector<int> v;
bitset<N> vis;
int min_cardinality(int N) {
// move_inside(i);
// move_outside(i);
// press_button(i);
n = N;
v.resize(n);
for (int i = 0; i < n; i++) v[i] = i;
shuffle(all(v), rng);
int mx = 1;
// Busco los primeros
m = 0;
for (int i = 0; i < n; i++) {
shuffle(v.begin()+i, v.end(), rng);
int x = v[i];
move_inside(x);
vis[x] = 1;
m++;
int y = press_button();
mx = max(mx, y);
if (y > 1) {
move_outside(x);
vis[x] = 0;
m--;
}
}
if (m == 1) return n;
int l = 1;
int r = min(n/m, (n-mx)/(m-1));
vector<int> to_remove;
int taken = m;
while (l < r) {
r = min(r, (n-mx)/(m-1));
int mid = (l+r+1)>>1;
shuffle(all(v), rng);
for (int i = 0; i < n && taken + (n-i) >= m*mid && taken < m*mid; i++) {
shuffle(v.begin()+i, v.end(), rng);
int x = v[i];
if (vis[x]) continue;
move_inside(x);
taken++;
vis[x] = 1;
int y = press_button();
mx = max(mx, y);
if (y > mid) {
move_outside(x);
taken--;
vis[x] = 0;
}
else {
to_remove.push_back(x);
}
}
if (taken == m*mid) l = mid;
else r = mid-1;
r = min(r, (n-mx)/(m-1));
if (taken != m*mid) {
shuffle(all(to_remove), rng);
while (!to_remove.empty()) {
shuffle(all(to_remove), rng);
int x = to_remove.back();
move_outside(x);
taken--;
vis[x] = 0;
to_remove.pop_back();
if (press_button() <= ((l+r+1)>>1)) break;
}
}
}
return l;
}
