#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
using ll = long long;
int count_mushrooms(int n) {
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;
}
if (n % 2 == 0) t[n-1] = use_machine({0, n-1});
for (int i = 3; i < n-1; 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;
return n - accumulate(t.begin(), t.end(), 0);
}
