#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e4 + 5;
const int SIZE = 100;
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);
};
if(pos[0].size() > 1){
int z = use_machine({3, pos[0][0], 4, pos[0][1]});
calc(3, 0, z & 1);
calc(4, 0, z >> 1);
}
else{
int z = use_machine({3, pos[1][0], 4, pos[1][1]});
calc(3, 1, z & 1);
calc(4, 1, z >> 1);
}
int cur = 5;
while(max(pos[0].size(), pos[1].size()) < SIZE){
int color = pos[0].size() > 2 ? 0 : 1, z = use_machine({cur, pos[color][0], cur + 1, pos[color][1], cur + 2, pos[color][2]});
calc(cur, color, z & 1);
if((z >> 1) != 1){
calc(cur + 1, color, z >> 2);
calc(cur + 2, a[cur + 1], 0);
cur += 3;
}
else if(pos[color ^ 1].size() > 1){
calc(cur + 4, color, (z = use_machine({pos[color ^ 1][0], cur + 1, pos[color ^ 1][1], pos[color][0], cur + 2, pos[color][1], cur + 3, pos[color][2], cur + 4}) - 1) & 1);
calc(cur + 3, color, (z >> 1) & 1);
calc(cur + 2, color, z >> 2);
calc(cur + 1, a[cur + 2], 1);
cur += 5;
}
else{
calc(cur + 1, 1, use_machine({0, cur + 1}));
calc(cur + 2, a[cur + 1], 1);
cur += 3;
}
}
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;
}
