/**
* Author : Nguyen Tuan Vu
* Created : 03.01.2023
**/
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + rng() % (r - l + 1);}
const int N = 2023;
int n;
int d;
int c;
bool used[N];
bool skip[N];
void move_inside(int i);
void move_outside(int i);
int press_button();
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) used[i] = true;
d = (int) p.size();
}
bool check(int x) {
c = 0;
for (int i = 0; i < n; i++)
c += used[i];
vector<int> ids;
for (int i = 0; i < n; i++)
if (!used[i] && !skip[i])
ids.push_back(i);
shuffle(ALL(ids), rng);
vector<int> p, q;
for (int i : ids) {
move_inside(i);
if (press_button() > x)
move_outside(i), q.push_back(i);
else
c++, p.push_back(i);
if (c == x * d)
break;
}
if (c == x * d) {
for (int i : p) used[i] = true;
return true;
} else {
for (int i : p) move_outside(i);
for (int i : q) skip[i] = true;
return false;
}
}
int min_cardinality(int N) {
n = N;
findDistinct();
if (d == 1)
return N;
// if (d == 2) {
// for (int i = 0; i < N; i++)
// if (!used[i])
// move_inside(i);
// return n - press_button();
// }
int l = 1, r = n / d + 1;
while(r - l > 1) {
int mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid, r = min(r, c / d + 1);
}
return l;
}
