#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int block = 140;
int count_mushrooms(int n) {
vector<bool> m(n, 0);
m[1] = use_machine({0, 1});
if (n == 2) return m[1] ? 1 : 2;
m[2] = use_machine({0,2});
int nx = 3;
vector<int> a = {0}, b;
if (m[1]) b.push_back(1);
else a.push_back(1);
if (m[2]) b.push_back(2);
else a.push_back(2);
auto first = [&](array<int, 2> t) {
while (nx+1 < n && max(a.size(), b.size()) < block) {
int q = use_machine({t[0], nx, t[1], nx+1});
if (q < 2) m[nx] = m[t[0]];
else m[nx] = !m[t[0]];
if ((q&1) == 1) m[nx+1] = !m[t[0]];
else m[nx+1] = m[t[0]];
if (m[nx]) b.push_back(nx);
else a.push_back(nx);
if (m[nx+1]) b.push_back(nx+1);
else a.push_back(nx+1);
nx += 2;
}
};
if (a.size() > 1) first({a[0], a[1]});
else first({b[0], b[1]});
long long tota = a.size();
auto second = [&](vector<int> &ts) {
vector<int> query;
for (int i = 0; i < ts.size() && i+nx < n; i++) {
query.push_back(ts[i]);
query.push_back(nx+i);
}
int hm = use_machine(query);
nx += ts.size();
tota += (m[ts[0]] ? (hm+1)/2 : query.size()/2 - (hm+1)/2);
if ((hm&1) == 1) {
if (m[ts[0]]) a.push_back(query.back());
else b.push_back(query.back());
}
};
while (nx < n) {
if (a.size() > b.size()) second(a);
else second(b);
}
return tota;
}
