#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define get use_machine
vector<int> a[2];
int cnt[2], id=1;
void f()
{
if (a[0].size()>=3)
{
int x=get({id,a[0][0],id+1,a[0][1],id+2,a[0][2]});
if (x%2) a[1].push_back(id);
else a[0].push_back(id);
if (x==4 or x==5)
a[1].push_back(id+1), a[1].push_back(id+2), id+=3;
if(!x or x==1)
a[0].push_back(id+1), a[0].push_back(id+2), id+=3;
if (x==2 or x==3)
{
a[x%2].push_back(id);
if (a[1].size()>=2)
{
int x=get({a[1][0],id+1,a[1][1],a[0][0],id+2,a[0][1],id+3,a[0][2],id+4})-1;
if (x&4) a[0].push_back(id+1), a[1].push_back(id+2);
else a[0].push_back(id+2), a[1].push_back(id+1);
if (x&2) a[1].push_back(id+3);
else a[0].push_back(id+3);
if (x%2) a[1].push_back(id+4);
else a[0].push_back(id+4);
id+=5;
}
else
{
int x=get({id+1,a[0][0],id+2,a[0][1],id+3,a[0][2]});
if (x>2) a[1].push_back(id+3);
else a[0].push_back(id+3);
if (x==1 or x==3) a[1].push_back(id+1), a[0].push_back(id+2);
else a[0].push_back(id+1), a[1].push_back(id+2);
id+=4;
}
}
}
else if (a[1].size()>=3)
{
int x=get({id,a[1-0][0],id+1,a[1-0][1],id+2,a[1-0][2]});
if (x%2) a[1-1].push_back(id);
else a[1-0].push_back(id);
if (x==4 or x==5)
a[1-1].push_back(id+1), a[1-1].push_back(id+2), id+=3;
if(!x or x==1)
a[1-0].push_back(id+1), a[1-0].push_back(id+2), id+=3;
if (x==2 or x==3)
{
a[x%2].push_back(id);
if (a[1-1].size()>=2)
{
int x=get({a[1-1][0],id+1,a[1-1][1],a[1-0][0],id+2,a[1-0][1],id+3,a[1-0][2],id+4})-1;
if (x&4) a[1-0].push_back(id+1), a[1-1].push_back(id+2);
else a[1-0].push_back(id+2), a[1-1].push_back(id+1);
if (x&2) a[1-1].push_back(id+3);
else a[1-0].push_back(id+3);
if (x%2) a[1-1].push_back(id+4);
else a[1-0].push_back(id+4);
id+=5;
}
else
{
int x=get({id+1,a[1-0][0],id+2,a[1-0][1],id+3,a[1-0][2]});
if (x>2) a[1-1].push_back(id+3);
else a[1-0].push_back(id+3);
if (x==1 or x==3) a[1-1].push_back(id+1), a[1-0].push_back(id+2);
else a[1-0].push_back(id+1), a[1-1].push_back(id+2);
id+=4;
}
}
}
else if (a[0].size()==2)
{
int x=get({id,a[0][0],id+1,a[0][1]});
if (x%2) a[1].push_back(id);
else a[0].push_back(id);
if (x>=2) a[1].push_back(id+1);
else a[0].push_back(id+1);
id+=2;
}
else if (a[1].size()==2)
{
int x=get({id,a[1][0],id+1,a[1][1]});
if (x%2) a[1].push_back(id);
else a[0].push_back(id);
if (x>=2) a[1].push_back(id+1);
else a[0].push_back(id+1);
id+=2;
}
else
{
int x=get({0,id});
a[x].push_back(id++);
}
}
int count_mushrooms(int n)
{
a[0]={0};
// if (n>10000)
// {
// while (id<200)
// f();
// }
while (id<n)
{
if (a[0].size()>=a[1].size())
{
vector<int> q;
int o=0;
for (int i=0;i<a[0].size() && id+i<n;i++)
q.push_back(a[0][i]), q.push_back(id+i), o++;
int x=get(q);
cnt[0]+=(x+1)/2-o, cnt[1]+=(x+1)/2;
id+=a[0].size();
if (x%2) a[1].push_back(q.back());
else a[0].push_back(q.back());
}
else
{
vector<int> q;
int o=0;
for (int i=0;i<a[1].size() && id+i<n;i++)
q.push_back(a[1][i]), q.push_back(id+i), o++;
int x=get(q);
cnt[1]+=(x+1)/2-o, cnt[0]+=(x+1)/2;
id+=a[1].size();
if (x%2) a[0].push_back(q.back());
else a[1].push_back(q.back());
}
}
return a[0].size()+cnt[0];
}
