#include <bits/extc++.h>
using namespace std;
const int MAXN = 2e4 + 24;
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;
}
int count_mushrooms(int n) {
if (n<=450) return f(n);
vector<int> a = {0}, b;
int acnt = 1, bcnt = 0, idx = 1;
// 물어봐서 개수 더하기
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 query = use_machine(q);
int p = query / 2;
if (a.size() >= b.size()) {
if (query & 1) b.push_back(idx - 1), p++;
else a.push_back(idx - 1);
acnt += qcnt - p, bcnt += p;
}
else {
if (query & 1) a.push_back(idx - 1), p++;
else b.push_back(idx - 1);
acnt += p, bcnt += qcnt - p;
}
// cout << acnt << ' ' << bcnt << endl;
}
return acnt;
}
