#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, mx, 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;
// Busco los primeros
m = 0;
shuffle(all(v), rng);
for (int i = 0; i < n; i++) {
int x = v[i];
move_inside(x);
vis[x] = 1;
m++;
if (press_button() > 1) {
move_outside(x);
vis[x] = 0;
m--;
}
}
if (m == 1) return n;
shuffle(all(v), rng);
for (int i = 0; i < n; i++) {
int x = v[i];
if (vis[x]) continue;
move_inside(x);
}
mx = press_button();
if (m == 2) {
return n-mx;
}
shuffle(all(v), rng);
for (int i = 0; i < n; i++) {
int x = v[i];
if (vis[x]) continue;
move_outside(x);
}
int l = 1;
int r = (n-mx)/(m-1);
vector<int> to_remove;
int taken = m;
while (l < r) {
shuffle(all(v), rng);
int mid = (l+r+1)>>1;
for (int i = 0; i < n && taken + (n-i) >= m*mid && taken < m*mid; i++) {
int x = v[i];
if (vis[x]) continue;
move_inside(x);
taken++;
vis[x] = 1;
if (press_button() > mid) {
move_outside(x);
taken--;
vis[x] = 0;
}
else {
to_remove.push_back(x);
}
}
if (taken != m*mid) {
for (int& x : to_remove) {
move_outside(x);
taken--;
vis[x] = 0;
}
to_remove.clear();
}
if (taken == m*mid) l = mid;
else r = mid-1;
}
return l;
}
