#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
const int LIM=80; //play with this
int n;
vector<int> red;
vector<int> blue;
int count_mushrooms(int N) {
n=N;
if (n<300){
int ans=1;
for (int x=1;x<n;x+=2){
if (x==n-1) ans+=1-use_machine({0,x});
else ans+=2-use_machine({x,0,x+1});
}
return ans;
}
red.push_back(0);
int idx=1;
while (sz(red)<2 && sz(blue)<2){
if (use_machine({0,idx})==0) red.push_back(idx++);
else blue.push_back(idx++);
}
rep(zzz,0,LIM){
if (sz(red)>=2){
int temp=use_machine({idx,red[0],idx+1,red[1]});
if (temp&1) blue.push_back(idx);
else red.push_back(idx);
if (temp&2) blue.push_back(idx+1);
else red.push_back(idx+1);
}
else{
int temp=use_machine({idx,blue[0],idx+1,blue[1]});
if (temp&1) red.push_back(idx);
else blue.push_back(idx);
if (temp&2) red.push_back(idx+1);
else blue.push_back(idx+1);
}
idx+=2;
}
int ans=sz(red);
//cout<<sz(red)<<" "<<sz(blue)<<endl;
while (idx<n){ //it is possible to save some queries here by using the last character but do it later (okay done)
vector<int> temp;
if (sz(red)>sz(blue)){
rep(x,0,sz(red)){
temp.push_back(red[x]);
if (idx+x<n) temp.push_back(idx+x);
}
int val=use_machine(temp);
ans+=sz(temp)-sz(red)-(val+1)/2;
idx+=sz(red);
if (val&1) blue.push_back(idx-1);
else red.push_back(idx-1);
}
else{
rep(x,0,sz(blue)){
temp.push_back(blue[x]);
if (idx+x<n) temp.push_back(idx+x);
}
int val=use_machine(temp);
ans+=(val+1)/2;
idx+=sz(blue);
if (val&1) red.push_back(idx-1);
else blue.push_back(idx-1);
}
}
return ans;
}
