#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> where, lastWhere;
void _move_inside(int x) {
where[x] = 1;
}
void _move_outside(int x) {
where[x] = 0;
}
map<vector<int>, int> memo;
int _press_button() {
if (memo.count(where)) return memo[where];
for (int i = 0; i < N; i++) {
if (where[i] == lastWhere[i]) continue;
if (where[i]) move_inside(i);
else move_outside(i);
}
lastWhere = where;
return memo[where] = press_button();
}
int min_cardinality(int n) {
N = n;
int D = 0;
where.resize(N), lastWhere.resize(N);
vector<int> can, in, out;
for (int i = 0; i < N; i++) {
_move_inside(i);
if (_press_button() == 2) {
_move_outside(i);
out.push_back(i);
} else {
D++;
in.push_back(i);
}
}
can = out;
int l = 2, r = N / D, ans = 1, cnt = D;
while (l <= r) {
int m = (l + r + 1) / 2;
in.resize(0), out.resize(0);
for (int i : can) {
if (cnt == D * m) {
out.push_back(i);
continue;
}
_move_inside(i);
if (_press_button() > m) {
_move_outside(i);
out.push_back(i);
} else {
in.push_back(i);
cnt++;
}
}
if (cnt == D * m) {
l = m + 1;
ans = m;
can = out;
} else {
r = m - 1;
can = in;
for (auto x : can) {
_move_outside(x);
cnt--;
}
}
}
return ans;
}
