#include "mushrooms.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
int count_mushrooms(int n) {
if(n<=220){
int ans=1;
for(int i=1;i<n;i++){
ans+=1-use_machine({0,i});
}
return ans;
}
int a=use_machine({0,1});
int b=use_machine({0,2});
vector<int> v[2];
v[0].push_back(0);
if(a){
v[1].push_back(1);
}
else{
v[0].push_back(1);
}
if(b){
v[1].push_back(2);
}
else{
v[0].push_back(2);
}
int y=0;
if(v[1].size()>=2){
y=1;
}
int u34=use_machine({3,v[y][0],4,v[y][1]});
if(u34%2==0){
v[y].push_back(3);
}
else{
v[y^1].push_back(3);
}
if(u34>=2){
v[y^1].push_back(4);
}
else{
v[y].push_back(4);
}
int r=5;
int ans=0;
while(r<n){
int z=0;
if(v[1].size()>v[0].size()){
z=1;
}
int w=min(n,r+(int)v[z].size());
vector<int> t;
for(int i=r;i<w;i++){
t.push_back(i);
t.push_back(v[z][i-r]);
}
int u=use_machine(t);
if(z==1){
ans+=u/2;
}
else{
ans+=(int)v[z].size()-(u/2)-1;
}
if(u%2==0){
v[z].push_back(r);
}
else{
v[z^1].push_back(r);
}
r=w;
}
ans+=v[0].size();
return ans;
}
