#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
int N;
vector<bool> cur, target;
map<vector<bool>, int> memo;
inline void mi(int i){ target[i] = true; }
inline void mo(int i){ target[i] = false; }
int pBtn() {
if (memo.count(target)) return memo[target];
for (int i = 0; i < N; ++i) {
if (cur[i] == target[i]) continue;
if (target[i]) move_inside(i);
else move_outside(i);
}
cur = target;
return memo[target] = press_button();
}
int min_cardinality(int _N) {
N = _N;
cur.assign(N, false);
target.assign(N, false);
vector<int> insects(N);
iota(insects.begin(), insects.end(), 0);
vector<int> insides, outsides;
int inside = 0;
for (int x : insects) {
mi(x);
if (pBtn() > 1) {
mo(x);
outsides.pb(x);
} else {
insides.pb(x);
++inside;
}
}
int distinct = inside;
insects = outsides;
int l = 1, r = N / distinct, ans = 1;
while (l <= r) {
int mid = (l + r + 1) / 2;
insides.clear();
outsides.clear();
for (int x : insects) {
mi(x);
if (pBtn() > mid) {
mo(x);
outsides.pb(x);
} else {
insides.pb(x);
++inside;
}
}
if (inside == mid * distinct) {
ans = mid;
l = mid + 1;
insects = outsides;
} else {
r = mid - 1;
insects = insides;
for (int x : insects) {
mo(x);
--inside;
}
}
}
return ans;
}
