#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e4 + 5;
const int SIZE = 136;
int a[lim];
vector<int>pos[2];
int count_mushrooms(int n){
pos[0].push_back(a[0] = 0);
if(n <= 553){
int ans = 1;
for(int i = 2; i < n; i += 2){
ans += 2 - use_machine({i - 1, 0, i});
}
if(~n & 1){
ans += 1 - use_machine({0, n - 1});
}
return ans;
}
for(int i = 1; i < 3; i++){
pos[a[i] = use_machine({0, i})].push_back(i);
}
auto calc = [&] (int i, int near, int z){
pos[a[i] = near ^ z].push_back(i);
};
int cur = 3;
while(max(pos[0].size(), pos[1].size()) < SIZE){
int color = pos[0].size() > 1 ? 0 : 1, z = use_machine({cur, pos[color][0], cur + 1, pos[color][1]});
calc(cur, color, z & 1);
calc(cur + 1, color, z >> 1);
cur += 2;
}
int ans = pos[0].size();
while(cur < n){
int color = pos[0].size() > pos[1].size() ? 0 : 1;
vector<int>ask;
for(int i = 0; i < pos[color].size() && cur < n; i++){
ask.push_back(cur++);
ask.push_back(pos[color][i]);
}
int z = use_machine(ask);
if(color == 0){
ans += (int(ask.size()) >> 1) - ((z + 1) >> 1);
}
else{
ans += (z + 1) >> 1;
}
calc(ask[0], color, z & 1);
}
return ans;
}
