#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const int sqr = 123;
int count_mushrooms(int n) {
vector <int> A, B;
A.push_back(0);
for(int i = 1;i < min(n, 2*((n+sqr-1)/sqr+1));i += 3){
// cout << i << ' ';
if(i+1 >= min(n, 2*((n+sqr-1)/sqr+1))){
int t = use_machine({0, i});
if(t == 1) B.push_back(i);
else A.push_back(i);
}
else if(i+2 >= min(n, 2*((n+sqr-1)/sqr+1))){
int t = use_machine({0, i});
if(t == 1) B.push_back(i);
else A.push_back(i);
t = use_machine({0,i+1});
if(t == 1) B.push_back(i+1);
else A.push_back(i+1);
}
else{
int t = use_machine({0, i, i+1, i+2});
if(t == 0){
A.push_back(i);
A.push_back(i+1);
A.push_back(i+2);
}
else if(t == 1){
t = use_machine({i+2, 0, i+1, i});
if(t == 1){
A.push_back(i);
A.push_back(i+1);
B.push_back(i+2);
}
else if(t == 3){
A.push_back(i);
B.push_back(i+1);
B.push_back(i+2);
}
else{
B.push_back(i);
B.push_back(i+1);
B.push_back(i+2);
}
}
else if(t == 2){
t = use_machine({0, i, i+2, i+1});
if(t == 1){
A.push_back(i);
B.push_back(i+1);
A.push_back(i+2);
}
if(t == 2){
B.push_back(i);
A.push_back(i+1);
A.push_back(i+2);
}
if(t == 3){
B.push_back(i);
B.push_back(i+1);
A.push_back(i+2);
}
}
else{
B.push_back(i);
A.push_back(i+1);
B.push_back(i+2);
}
}
}
//cout << endl;
int st = max(A.back(), (B.empty() ? -1 : B.back()));
st++;
if(st == n) return A.size();
int typ = (A.size() >= B.size() ? 0 : 1);
int res = A.size();
for(int i = st;i < min(n, st+sqr);i++){
vector <int> query;
int x = i;
int con = 0;
while(x < n){
query.push_back((typ == 0 ? A[(x-st)/(sqr)] : B[(x-st)/(sqr)]));
query.push_back(x);
con += 2;
x += sqr;
}
query.push_back((typ == 0 ? A.back() : B.back()));
/*for(auto x : query){
cout << x << ' ';
}*/
//cout << endl;
res += (typ == 0 ? (con-use_machine(query))/2 : use_machine(query)/2);
}
return res;
}
