#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#include "mushrooms.h"
int count_mushrooms(int n){
vector<int> s[2]={{0},{}};
int nn[2]={0,0};
vector<int> ns;
for(int i=1;i<n;i++)ns.pb(i);
int k=85;
while(ns.size()>0){
if(k>0 && ns.size()>1 && max(s[0].size(),s[1].size())>1){
k--;
int a=ns[ns.size()-1];
int b=ns[ns.size()-2];
ns.pop_back();
ns.pop_back();
bool si=1;
if(s[0].size()>s[1].size())si=0;
vector<int> v={s[si][0],a,s[si][1],b};
int x=use_machine(v);
if(x%2)s[!si].pb(b);
else s[si].pb(b);
x=x/2;
if(x%2)s[!si].pb(a);
else s[si].pb(a);
}
else{
bool si=1;
if(s[0].size()>s[1].size())si=0;
int tam=min(s[si].size(),ns.size());
vector<int> v(2*tam);
for(int i=0;i<tam;i++){
v[2*i]=s[si][i];
}
for(int i=0;i<tam;i++){
v[2*i+1]=ns[ns.size()-i-1];
}
for(int i=0;i<tam;i++)ns.pop_back();
int x=use_machine(v);
if(x%2)s[!si].pb(v[2*tam-1]);
else s[si].pb(v[2*tam-1]);
x=x/2;
nn[!si]+=x;
nn[si]+=tam-1-x;
}
}
return s[0].size()+nn[0];
}
