#include "mushrooms.h"
//#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end();
int count_mushrooms(int n) {
vector<int> a[2];
a[0].pb(0);
int last=1;
for(int i=1;i<n && max(a[0].size(),a[1].size())<2;i++){
if(use_machine({0,i})) a[1].pb(i);
else a[0].pb(i);
last++;
}
for(int i=last;i+1<n && (int)a[0].size()<100 && (int)a[1].size()<100;){
int x=0;
if(a[0].size()<2) x=1;
int cnt=use_machine({a[x][0],i,a[x][1],i+1});
if(cnt==0) {a[x].pb(i);a[x].pb(i+1);}
if(cnt==1) {a[x].pb(i);a[x^1].pb(i+1);}
if(cnt==2) {a[x].pb(i+1);a[x^1].pb(i);}
if(cnt==3) {a[x^1].pb(i);a[x^1].pb(i+1);}
i+=2;
last=i;
}
vector<int> A(2);
for(int i=last;i<n;){
int x=0,s=a[0].size();
if(s<(int)a[1].size()) x=1,s=a[1].size();
int l=min(i+s,n);
vector<int> v;
for(int j=i;j<l;j++){
v.pb(a[x][j-i]);
v.pb(j);
}
int cnt=use_machine(v);
if(cnt%2) A[x^1]++,a[x^1].pb(l-1),cnt--;
else A[x]++,a[x].pb(l-1);
A[x^1]+=(cnt+1)/2,A[x]+=(l-i-1-(cnt+1)/2);
i=l;
}
return A[0];
}
