#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=1e5+10,K=142;
int count_mushrooms(int n)
{
if (n<=400)
{
int cnt=1;
for (int i=1;i<n;i+=2)
{
vi vt;
vt.eb(i);
vt.eb(0);
if (i+1<n) vt.eb(i+1);
cnt+=vt.size()-1-use_machine(vt);
}
return cnt;
}
vi S[2];
S[0].eb(0);
int len=1;
int i=1;
while (len<2)
{
vi vt={0,i};
S[use_machine(vt)].eb(i++);
len=max(S[0].size(),S[1].size());
}
int inv=0,v1,v2;
if (S[0].size()==2)
{
v1=S[0][0];
v2=S[0][1];
}
else
{
v1=S[1][0];
v2=S[1][1];
inv=1;
}
while (len<K)
{
vi vt;
vt.eb(i);
vt.eb(v1);
if (i+1<n) vt.eb(i+1),vt.eb(v2);
int tmp=use_machine(vt);
S[(tmp&1)^inv].eb(i++);
if (vt.size()==4)
S[((tmp>>1)&1)^inv].eb(i++);
len=max(S[0].size(),S[1].size());
}
if ((int)S[0].size()==len) inv=0;
else inv=1;
int res=S[0].size();
while (i<n)
{
vi vt={S[inv][0]};
for (int j=1;j<len && i<n;j++)
{
vt.eb(i++);
vt.eb(S[inv][j]);
}
int tmp=use_machine(vt);
if (inv) res+=tmp/2;
else res+=vt.size()/2-tmp/2;
}
return res;
}
