#include "insects.h"
#include <bits/stdc++.h>
#include <random>
using namespace std;
mt19937 mt;
#define qry press_button
vector<int> p;
bitset<2000> bs, bs1, bs2, bs3, bs4;
int numinc = 0;
void add(int n) {
n = p[n];
if (!bs[n]) {
move_inside(n);
numinc++;
}
bs[n] = 1;
}
void rem(int n) {
n = p[n];
if (bs[n]) {
move_outside(n);
numinc--;
}
bs[n] = 0;
}
int min_cardinality(int N) {
mt = mt19937(100);
for (int i = 0; i < N; i++) p.push_back(i);
shuffle(p.begin(), p.end(), mt);
int numu = 0;
for (int i = 0; i < N; i++) {
add(i);
if (qry() > 1) rem(i);
else numu++;
}
int low = 2, high = N / numu, ans = 1;
while (low <= high) {
int x = (low + high) / 2;
bs2 = 0;
for (int i = 0; i < N && numinc != numu * x; i++) {
if (bs1[i] || bs3[i] || bs[i]) continue;
add(i);
if (qry() > x) {
rem(i);
bs1[i] = 1;
}
else bs2[i] = 1;
}
if (numinc == numu * x) low = x + 1, ans = x, bs1 = bs4, bs3 |= bs2;
else {
high = x - 1;
for (int i = 0; i < N; i++) if (bs2[i] && !bs3[i]) rem(i);
bs4 = bs1;
}
}
return ans;
}
