#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n)
{
if(n<=4)
{
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 a, b, x=0;
if(v[0].size()>=2)a=v[0][0],b=v[0][1];
else a=v[1][0],b=v[1][1],x=1;
int bu=(int)sqrt(n);
for(int i=1;i++<bu;)
{
vector<int>q;
q.push_back(a);q.push_back(2*i-1);q.push_back(b);q.push_back(2*i);
int ans=use_machine(q);
if(ans<2)v[x].push_back(2*i-1);
else v[1-x].push_back(2*i-1);
if(ans%2==0)v[x].push_back(2*i);
else v[1-x].push_back(2*i);
}
int jump;
int ret=v[0].size();
for(int i=2*bu+1;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;
}
