#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 20;
const int lim = 94;
int order[maxn];
vector<int> group[maxn];
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
int count_mushrooms(int n) {
for (int i = 0; i < n; i++) {
order[i] = i;
}
shuffle(order + 1, order + n, gen);
int pt = 1;
group[0].push_back(0);
int cur = 0;
while (pt < n && (int)group[0].size() < lim && (int)group[1].size() < lim) {
cur ^= use_machine({order[pt - 1], order[pt]});
group[cur].push_back(order[pt]);
pt++;
}
int g = (int)group[0].size() >= lim ? 0 : 1;
int res = (int)group[0].size();
for (; pt < n;) {
int k = min((int)group[g].size(), n - pt);
vector<int> a;
for (int i = 0; i < k; i++) {
a.push_back(group[g][i]);
a.push_back(order[pt + i]);
}
if (g == 0) {
res += k - (use_machine(a) + 1) / 2;
}
else {
res += (use_machine(a) + 1) / 2;
}
pt += k;
}
return res;
}
