#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define get use_machine
int count_mushrooms(int n)
{
vector<int> v={0},v1;
int j=n;
for (int i=1;i<n;i+=2)
{
int mx=max(v.size(),v1.size());
if (mx*mx>=n-i)
{
j=i;
break;
}
int x=get({i+1,0,i});
if (x==0)
v.push_back(i), v.push_back(i+1);
else if(x==2)
v1.push_back(i), v1.push_back(i+1);
else
{
if (get({i+1,0}))
v.push_back(i), v1.push_back(i+1);
else
v.push_back(i+1), v1.push_back(i);
}
}
bool b=0;
int ans=v.size();
if (v.size()<v1.size())
swap(v,v1), b=1;
int m=v.size();
for (int it=j;it<n;it+=m)
{
vector<int> c;
int id=0,tot=0;
for (int l=it;l<min(n,it+m);l++)
c.push_back(v[id++]), c.push_back(l), tot++;
int x=get(c);
if (b)
ans+=(x+1)/2;
else
ans+=tot-(x+1)/2;
}
return ans;
}
