#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 100005
#define k 140
int ca,cb,now;
vector<int> a,b;
void ch(int x){
if(use_machine({0,x}))b.push_back(x);
else a.push_back(x);
}
int count_mushrooms(int n){
int i,j,val;
a.push_back(0);
now=1;
if(n<285){
for(i=1;i<n;i++)ch(i);
return a.size();
}
ch(now++);
if(a.size()<2)ch(now++);
if(a.size()==2){
while(a.size()<k&&b.size()<k){
val=use_machine({a[0],now,a[1],now+1});
if(val==0)a.push_back(now),a.push_back(now+1);
else if(val==1)a.push_back(now),b.push_back(now+1);
else if(val==2)b.push_back(now),a.push_back(now+1);
else if(val==3)b.push_back(now),b.push_back(now+1);
now+=2;
}
}
else{
while(a.size()<k&&b.size()<k){
val=use_machine({b[0],now,b[1],now+1});
if(val==0)b.push_back(now),b.push_back(now+1);
else if(val==1)b.push_back(now),a.push_back(now+1);
else if(val==2)a.push_back(now),b.push_back(now+1);
else if(val==3)a.push_back(now),a.push_back(now+1);
now+=2;
}
}
if(a.size()>=k){
vector<int> v;
while(now+a.size()<=n){
for(auto x:a)v.push_back(x),v.push_back(now++);
cb+=(use_machine(v)+1)/2;
v.clear();
}
i=0;
while(now<n){
v.push_back(a[i++]);
v.push_back(now++);
}
if(!v.empty())cb+=(use_machine(v)+1)/2;
return n-b.size()-cb;
}
else{
vector<int> v;
while(now+b.size()<=n){
for(auto x:b)v.push_back(x),v.push_back(now++);
ca+=(use_machine(v)+1)/2;
v.clear();
}
i=0;
while(now<n){
v.push_back(b[i++]);
v.push_back(now++);
}
if(!v.empty())ca+=(use_machine(v)+1)/2;
return a.size()+ca;
}
}
