#include <bits/stdc++.h>
using namespace std;
#include "mushrooms.h"
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int count_mushrooms(int n) {
if(n==2) return 1+(1-use_machine({1,0}));
vector<int> aa;
aa.pb(0);
vector<int> bb;
int lst=3;
vector<int> per;
for (int i = 0; i < n; ++i) per.pb(i);
shuffle(per.begin()+1,per.end(),rng);
( use_machine({0,per[1]}) ? bb.pb(per[1]) : aa.pb(per[1]));
( use_machine({0,per[2]}) ? bb.pb(per[2]) : aa.pb(per[2]));
for (int i = 3; i+1 < min(n,284); i+=2)
{
if(aa.size()>=141||bb.size()>=141) break;
lst=i+2;
int cur;
if(aa.size()>=2){
cur=use_machine({per[i],aa[0],per[i+1],aa[1]});
if(cur==0){
aa.pb(per[i]);
aa.pb(per[i+1]);
}else if(cur==1){
bb.pb(per[i]);
aa.pb(per[i+1]);
}else if(cur==2){
aa.pb(per[i]);
bb.pb(per[i+1]);
}else if(cur==3){
bb.pb(per[i]);
bb.pb(per[i+1]);
}
}
else{
cur=use_machine({per[i],bb[0],per[i+1],bb[1]});
if(cur==0){
bb.pb(per[i]);
bb.pb(per[i+1]);
}else if(cur==1){
aa.pb(per[i]);
bb.pb(per[i+1]);
}else if(cur==2){
bb.pb(per[i]);
aa.pb(per[i+1]);
}else if(cur==3){
aa.pb(per[i]);
aa.pb(per[i+1]);
}
}
}
int ans=aa.size();
for (int i = lst; i < n; i+=140)
{
vector<int> cur;
int k=0;
for (int j = 0; j < min(n-i,140); ++j)
{
cur.pb(per[i+j]);
cur.pb((aa.size()>bb.size() ? aa[k++] : bb[k++]));
}
int cnt=use_machine(cur);
cnt++;
ans+=(aa.size()<=bb.size() ? cnt/2 : cur.size()-k-cnt/2);
if((cnt-1)%2) ((aa.size()>bb.size() ? bb.pb(per[i]) : aa.pb(per[i])));
}
return ans;
}
