#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
template<typename T>
int len(T &a){return a.size();}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int count_mushrooms(int n) {
if(n < 226){
int ans = 1;
for(int i = 1; i < n; i ++){
ans += use_machine({0, i}) ^ 1;
}
return ans;
}
vector<int> a = {0}, b;
int i = 1;
while(len(a) < 2 && len(b) < 2){
if(use_machine({0, i})){
b.push_back(i);
}else{
a.push_back(i);
}
i ++;
}
int sq = 90;
while(len(a) < sq && len(b) < sq && i < n){
if(len(a) >= 2){
int cnt = use_machine({a[0], i, a[1], i + 1});
if(cnt == 0){
a.push_back(i);
a.push_back(i + 1);
}
if(cnt == 1){
a.push_back(i);
b.push_back(i + 1);
}
if(cnt == 2){
b.push_back(i);
a.push_back(i + 1);
}
if(cnt == 3){
b.push_back(i);
b.push_back(i + 1);
}
i += 2;
}else{
int cnt = use_machine({b[0], i, b[1], i + 1});
if(cnt == 3){
a.push_back(i);
a.push_back(i + 1);
}
if(cnt == 2){
a.push_back(i);
b.push_back(i + 1);
}
if(cnt == 1){
b.push_back(i);
a.push_back(i + 1);
}
if(cnt == 0){
b.push_back(i);
b.push_back(i + 1);
}
i += 2;
}
}
if(len(a) >= len(b)){
ll ans = len(a);
while(i < n){
vector<int> req;
for(int j = 0; j < len(a) && i < n; j ++){
req.push_back(a[j]);
req.push_back(i);
i ++;
}
int cnt = use_machine(req);
ans += len(req) / 2 - (cnt + 1) / 2;
if(cnt & 1){
b.push_back(req.back());
}else a.push_back(req.back());
}
return ans;
}else{
ll ans = len(a);
while(i < n){
vector<int> req;
for(int j = 0; j < len(b) && i < n; j ++){
req.push_back(b[j]);
req.push_back(i);
i ++;
}
int cnt = use_machine(req);
ans += (cnt + 1) / 2;
if(cnt & 1){
a.push_back(req.back());
}else b.push_back(req.back());
}
return ans;
}
}
