#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n)
{
if(n<=200)
{
int ans=1;
for(int i=1;i<n;i++)
{
vector<int>v;
v.push_back(0);v.push_back(i);
if(use_machine(v)==0)ans++;
}
return ans;
}
vector<int>v[2];
v[0].push_back(0);
vector<int>qr;
qr.push_back(0);qr.push_back(1);
v[use_machine(qr)].push_back(1);
qr.pop_back();qr.push_back(2);
v[use_machine(qr)].push_back(2);
int y=0;
if(v[0].size()<2)y=1;
qr.clear();
qr.push_back(v[y][0]);
qr.push_back(3);
qr.push_back(v[y][1]);
qr.push_back(4);
int ans=use_machine(qr);
v[(ans/2+y)%2].push_back(3);
v[(ans+y)%2].push_back(4);
int x=0;
if(v[0].size()<3)x=1;
int bu=45;
for(int i=1;i<bu;i++)
{
vector<int>q;
q.push_back(v[x][0]);q.push_back(5*i);q.push_back(v[x][1]);q.push_back(5*i+1);q.push_back(v[x][2]);q.push_back(5*i+2);
int ans=use_machine(q);
if(ans/2==1)
{
v[(ans+x)%2].push_back(5*i+2);
if(v[1-x].size()<2)
{
vector<int>qr;
qr.push_back(v[x][0]);
qr.push_back(5*i+3);
qr.push_back(v[x][1]);
qr.push_back(5*i+4);
int ans=use_machine(qr);
v[(ans/2+x)%2].push_back(5*i+3);
v[(ans+x)%2].push_back(5*i+4);
qr.clear();
qr.push_back(v[x][0]);
qr.push_back(5*i);
ans=use_machine(qr);
v[(ans+x)%2].push_back(5*i);
v[(ans+x+1)%2].push_back(5*i+1);
}
else
{
vector<int>qr;
qr.push_back(v[1-x][0]);
qr.push_back(5*i);
qr.push_back(v[1-x][1]);
qr.push_back(v[x][0]);
qr.push_back(5*i+1);
qr.push_back(v[x][1]);
qr.push_back(5*i+3);
qr.push_back(v[x][2]);
qr.push_back(5*i+4);
int ans=use_machine(qr);
ans--;
v[(ans/4+x+1)%2].push_back(5*i);
v[(ans/4+x)%2].push_back(5*i+1);
ans%=4;
v[(ans/2+x)%2].push_back(5*i+3);
v[(ans+x)%2].push_back(5*i+4);
}
}
else
{
v[(ans/4+x)%2].push_back(5*i);
v[(ans/4+x)%2].push_back(5*i+1);
v[(ans+x)%2].push_back(5*i+2);
vector<int>qr;
qr.push_back(v[x][0]);
qr.push_back(5*i+3);
qr.push_back(v[x][1]);
qr.push_back(5*i+4);
int ans=use_machine(qr);
v[(ans/2+x)%2].push_back(5*i+3);
v[(ans+x)%2].push_back(5*i+4);
}
}
int jump;
int ret=v[0].size();
for(int i=5*bu;i<n;i+=jump)
{
int k;
if(v[0].size()>v[1].size())
{
k=0;
jump=v[0].size();
}
else
{
k=1;
jump=v[1].size();
}
vector<int>quer;
for(int j=i;j<min(i+jump, n);j++)
{
quer.push_back(v[k][j-i]);
quer.push_back(j);
}
int ans=use_machine(quer);
if(k)ret+=(ans/2+ans%2);
else ret-=(ans/2+ans%2),ret+=(min(i+jump, n)-i);
v[(ans%2)^k].push_back(min(i+jump, n)-1);
}
return ret;
}
