#include "mushrooms.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
int count_mushrooms(int n) {
if(n == 2)
return 2 - use_machine({0, 1});
vector<int> A[2];
A[0].pb(0);
int res = use_machine({0, 1});
int x = 2;
if(res){
A[1].pb(1);
res = use_machine({0, 2});
x = 3;
if(res) A[1].pb(2);
else A[0].pb(2);
} else A[0].pb(1);
vector<int> rem;
int lim = 100;
for(int _ = 0; _ < lim; _ ++){
if(x + 1 >= n) break;
int id = 1;
if(A[0].size() >= A[1].size()) id = 0;
int r1 = x, r2 = x + 1; x += 2;
res = use_machine({ r1, A[id][0], r2, A[id][1]});
A[id ^ (res & 1)].pb(r1);
A[id ^ (res >>1)].pb(r2);
}
vector<int> c(2, 0);
while(x < n){
int id = 1;
if(A[0].size() >= A[1].size()) id = 0;
int mx = A[id].size();
int dl = min(mx, n - x);
vector<int> ASK;
for(int j = 0; j < dl; j++){
ASK.pb(x + j);
ASK.pb(A[id][j]);
}
int mid = dl - 1;
A[id ^ (res & 1)].pb(x);
c[id ^ 1] += res / 2;
c[id] += (mid - (res / 2));
x += dl;
}
return c[0] + A[0].size();
}
