#include "insects.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#ifdef LOCAL
#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int N = 2023;
int n;
int d;
bool used[N];
void findDistinct() {
vector<int> p;
for (int i = 0; i < n; i++) {
move_inside(i);
if (press_button() == 1)
p.push_back(i);
else
move_outside(i);
}
for (int i : p)
move_outside(i);
d = (int) p.size();
}
bool check(int x) {
vector<int> p;
for (int i = 0; i < n; i++) if (!used[i]) {
move_inside(i);
if (press_button() > x)
move_outside(i);
else
p.push_back(i);
}
int c = (int) p.size();
for (int i = 0; i < n; i++)
c += used[i];
if (c == x * d) {
for (int i : p) used[i] = true;
return true;
} else {
for (int i : p) move_outside(i);
return false;
}
}
int min_cardinality(int N) {
n = N;
findDistinct();
int l = 0, r = n / d + 1;
while(r - l > 1) {
int mid = (l + r) / 2;
if (check(mid))
l = mid, r = min(r, n / l + 1);
else
r = mid;
}
return l;
}
