#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()
int count_mushrooms(int n) {
if(n<220)
{
vector<int> m(3,0);
ll c2=1;
for(int i=1;i<n-1;i+=2)
{
m[0]=i;
m[2]=i+1;
int c1 = use_machine(m);
c2+=2-c1;
}
if(n%2==0)
{
m.clear();
m.assign(2,0);
m[1]=n-1;
int c1 = use_machine(m);
if(!c1)
c2++;
}
return c2;
}
vector<int>A,B;
A.pb(0);
int i;
ll tf=1;
ll a=use_machine({0,1});
if(a==0)
{
A.pb(-1);
A.pb(1);
}
else
{
tf=2;
B.pb(1);
a=use_machine({0,2});
if(a==0)
{
A.pb(-1);
A.pb(2);
}
else
{
B.pb(-1);
B.pb(2);
tf=3;
}
}
for(i=((tf==1)?2:3);i<202;i+=2)
{
if(tf<=2)
{
ll ans=use_machine({0,i,A[2],i+1});
if(ans<2)
{
A.pb(-1);
A.pb(i);
}
else
{
if(B.size()!=0)
B.pb(-1);
B.pb(i);
}
if(A.size()==201 || B.size()==201)
break;
if(ans%2==0)
{
A.pb(-1);
A.pb(i+1);
}
else
{
if(B.size()!=0)
B.pb(-1);
B.pb(i+1);
}
if(A.size()==201 || B.size()==201)
{
i++;
break;
}
}
else
{
ll ans=use_machine({1,i,2,i+1});
if(ans>=2)
{
A.pb(-1);
A.pb(i);
}
else
{
if(B.size()!=0)
B.pb(-1);
B.pb(i);
}
if(A.size()==201 || B.size()==201)
break;
if(ans%2)
{
A.pb(-1);
A.pb(i+1);
}
else
{
if(B.size()!=0)
B.pb(-1);
B.pb(i+1);
}
if(A.size()==201 || B.size()==201)
{
i++;
break;
}
}
}
ll counta=A.size()/2 + 1;
i++;
for(i=i;i<n;i+=100)
{
if(A.size()==201)
{
if(i+100<=n)
{
for(int j=0;j<100;j++)
A[j*2+1]=i+j;
ll ans=use_machine(A);
counta+=100-ans/2;
continue;
}
vector<int>p;
int j;
for(j=0;j<n-i;j++)
{
p.pb(A[j*2]);
p.pb(i+j);
}
p.pb(A[j*2]);
ll ans=use_machine(p);
counta+=(n-i)-ans/2;
}
else
{
if(i+100<=n)
{
for(int j=0;j<100;j++)
B[j*2+1]=i+j;
ll ans=use_machine(B);
counta+=ans/2;
continue;
}
vector<int>p;
int j;
for(j=0;j<n-i;j++)
{
p.pb(B[j*2]);
p.pb(i+j);
}
p.pb(B[j*2]);
ll ans=use_machine(p);
counta+=ans/2;
}
}
return counta;
}
