#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()
int count_mushrooms(int n) {
if(n<=4)
{
bool tf=0;
ll o=use_machine({0,1});
if(n==2)
return 2 - o;
int p1=0,p2=1;
ll count=1;
if(!o)
count++;
ll oo=use_machine({0,2});
if(!oo)
count++;
if(o)
{
if(o==oo)
{
p1=1;
p2=2;
tf=1;
}
else
p2=2;
}
for(int i=3;i<n-1;i+=2)
{
ll x=use_machine({p1,i,p2,i+1});
//cout<<x<<' ';
if(tf)
count+= x/2 + x%2;
else
count+=2 - (x/2 + x%2);
}
if(n%2==0)
count+= 1 - use_machine({0,n-1});
return count;
}
vector<vector<int>>v(2,vector<int>());
v[0].pb(0);
ll o=use_machine({0,1});
v[o].pb(1);
o=use_machine({0,2});
v[o].pb(2);
bool tf;
if(v[1].size()==2)
tf=1;
for(int i=3;i<=145;i+=2)
{
ll x=use_machine({v[tf][0],i,v[tf][1],i+1});
if(tf)
{
v[tf - x/2].pb(i);
v[tf - x%2].pb(i+1);
}
else
{
v[x/2].pb(i);
v[x%2].pb(i+1);
}
}
ll sz=146;
ll count=v[0].size();
ll maxi;
for(int i=147;i<n - sz;i+=sz)
{
maxi=i+sz;
vector<int>ans;
ll idx=0;
for(int j=0;j<sz;j++)
{
if(idx<v[0].size())
ans.pb(v[0][idx]);
else
ans.pb(v[1][idx-v[0].size()]);
ans.pb(i+j);
idx++;
}
ll x=use_machine(ans);
ll sz0=v[0].size(),sz1=v[1].size();
ll xx=0;
ans.clear();
if(v[1].size())
{
x-=2;
for(int j=0;j<v[0].size();j++)
{
ans.pb(v[0][j]);
ans.pb(i+j);
}
xx=use_machine(ans);
count+=sz0 - (xx/2 + xx%2) + (x-(xx-xx%2))/2 + (x-(xx-xx%2))%2;
v[xx%2].pb(i+sz0-1);
v[1-x%2].pb(i+sz-1);
}
else
{
count+=sz0 - (x/2 + x%2);
v[1-x%2].pb(i+sz-1);
}
}
if(maxi!=n)
{
ll idx=0;
vector<int>ans;
for(int i=maxi;i<n;i++)
{
if(idx<v[0].size())
ans.pb(v[0][idx]);
else
ans.pb(v[1][idx-v[0].size()]);
ans.pb(i);
idx++;
}
ll x=use_machine(ans);
ll sz0=v[0].size(),sz1=v[1].size();
ll xx=0;
ans.clear();
if(n-maxi>v[0].size())
{
x-=2;
for(int j=0;j<v[0].size();j++)
{
ans.pb(v[0][j]);
ans.pb(maxi+j);
}
xx=use_machine(ans);
count+=sz0 - (xx/2 + xx%2) + (x-(xx-xx%2))/2 + (x-(xx-xx%2))%2;
}
else
count+=sz0 - (x/2 + x%2);
}
return count;
}
