#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
using ll = long long;
int count_mushrooms(int n) {
const int B = 281; // sqrt(4n)
vector<int> t(n);
t[1] = use_machine({0, 1});
if (n == 2) return 2 - t[1] - t[0];
t[2] = use_machine({0, 2});
bool inv = false;
int cmp1, cmp2;
if (t[1] && t[2]) {
cmp1 = 1;
cmp2 = 2;
inv = true;
t[0] ^= 1;
t[1] ^= 1;
t[2] ^= 1;
} else {
cmp1 = 0;
if (!t[1]) cmp2 = 1;
else cmp2 = 2;
}
for (int i = 3; i < n-1 && i < B; i += 2) {
int res = use_machine({cmp1, i, cmp2, i+1});
t[i] = res / 2;
t[i+1] = res % 2;
}
if (inv)
for (int& i : t)
i ^= 1;
if (n < B && n % 2 == 0)
t[n-1] = use_machine({0, n-1});
int ans = n - accumulate(t.begin(), t.end(), 0);
if (n <= B) return ans;
vector<int> As, Bs;
for (int i = 0; i < B; i++) {
if (t[i] == 0) As.push_back(i);
else Bs.push_back(i);
}
vector<int> grp = As.size() > Bs.size() ? As : Bs;
for (int j = B; j < n; j += B / 2) {
vector<int> inter;
for (int k = j; k < n && k < j + B / 2; k++)
inter.push_back(j);
vector<int> cur;
for (int i = 0; i < (int)inter.size(); i++) {
cur.push_back(grp[i]);
cur.push_back(inter[i]);
}
cur.push_back(grp[inter.size()]);
int cnt = use_machine(cur);
assert(cnt % 2 == 0);
cnt /= 2;
if (grp == Bs) {
ans += cnt;
} else {
ans += inter.size() - cnt;
}
}
return ans;
}
