#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
int cnt= 0;
struct segTree{
int dd, htt, val, mid;
segTree *L, *R;
segTree(int l, int r, int vale){
dd=l, htt=r;
mid=(dd+htt)/2;
if(vale!=-1)val=vale;
else{
vector<int>temp;
for(int i = dd; i<= htt ; i++){
temp.PB(i);
}
if(cnt<20000)val=use_machine(temp);
else return;
cnt++;
}
//cout<<dd<<" "<<htt<<" "<<val<<endl;
if(val==0||val==(htt-dd)){
}else{
if(l+1<r){
L = new segTree(l, mid, -1);
R = new segTree(mid, r, val-L->val);
}
}
}
int ask(int l, int r){
if(val==0){
return 0;
}
if(val==(htt-dd)){
return 1;
}
if(l==dd&&r==htt)return val;
if(r<=mid){
return L->ask(l , r);
}else{
return R->ask(l, r);
}
}
};
int count_mushrooms(int n) {
vector<int> rta, m;
int fin = 0;
rta.PB(0);
segTree *tree = new segTree(0, n-1, -1);
for(int i = 0 ; i < n-1 ; i++){
if(rta.back()==0)fin++;
int ans;
//m.PB(i), m.PB(i+1);
ans = tree->ask(i, i+1);
if(ans){
rta.PB(abs(rta.back()-1));
}else{
rta.PB(rta.back());
}
m.pop_back();
m.pop_back();
}
if(rta.back()==0)fin++;
return fin;
}
