#include <bits/extc++.h>
using namespace std;
int use_machine(vector<int> x);
int f(int n) {
int b = 0;
for (int i = 1; i + 1 < n; i += 2) b += use_machine({i, 0, i + 1});
if ((n & 1) == 0) b += use_machine({0, n - 1});
return n - b;
}
// sqrt(20000) = 141.xx
int count_mushrooms(int n) {
if (n <= 450) return f(n);
vector<int> a = {0}, b;
int acnt = 1, bcnt = 0, idx = 1, s = sqrt(20000);
while (max(a.size(), b.size()) < s && idx < n) {
if (use_machine({idx, 0})) b.push_back(idx++), bcnt++;
else a.push_back(idx++), acnt++;
}
while (idx < n) {
vector<int> q, &c = (a.size() >= b.size()) ? a : b;
int qcnt = 0;
for (int i = 0; i < c.size() && idx < n; i++) q.push_back(c[i]), q.push_back(idx++), qcnt++;
// for (auto qq: q) cout << qq << ' ';
// cout << endl;
int ret = use_machine(q);
int p = ret / 2 + (ret & 1);
if (a.size() >= b.size()) {
if (ret & 1) b.push_back(idx - 1);
else a.push_back(idx - 1);
acnt += qcnt - p, bcnt += p;
}
else {
if (ret & 1) a.push_back(idx - 1);
else b.push_back(idx - 1);
acnt += p, bcnt += qcnt - p;
}
// cout << acnt << ' ' << bcnt << endl;
}
return acnt;
}
