#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define get use_machine
int count_mushrooms(int n)
{
vector<int> a[2];a[0]={0};
a[get({0,1})].push_back(1);
if (n==2) return a[0].size();
if (a[0].size()==1)
a[get({0,2})].push_back(2);
int c=0;
if (a[1].size()==2) c=1;
bool vis[n]={}; vis[0]=vis[1]=vis[2]=1;
srand(time(NULL));
while (a[0].size()+a[1].size()+1<n && max(a[0].size(),a[1].size())<137)
{
int x,y,z;
while (1)
{
z=rand()%n;
if (!vis[z])
{
x=z, vis[x]=1;
break;
}
}
while (1)
{
z=rand()%n;
if (!vis[z])
{
y=z, vis[y]=1;
break;
}
}
z=get({x,a[c][0],y,a[c][1]});
a[c^(z%2)].push_back(x);
a[c^(z>=2)].push_back(y);
}
vector<int> v;
for (int i=0;i<n;i++)
if (!vis[i]) v.push_back(i);
c=0;
int val[2];val[0]=a[0].size(), val[1]=a[1].size();
if (a[1].size()>a[0].size()) c=1;
while (v.size())
{
int tot=1;
vector<int> q={v.back()};v.pop_back();
for (int i=0;i+1<a[c].size() && v.size();i++)
q.push_back(a[c][i]), q.push_back(v.back()), v.pop_back(), tot++;
q.push_back(a[c].back());
int x=get(q);x=(x+1)/2;
val[c]+=tot-x, val[1-c]+=x;
}
return val[0];
}
