#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const int sqr = 100;
int count_mushrooms(int n) {
vector <int> A, B;
A.push_back(0);
for(int i = 1;i < n;i++){
if(A.size() >= (n+sqr-1)/sqr+1 or B.size() >= (n+sqr-1)/sqr+1) continue;
int t = use_machine({0, i});
if(t == 1) B.push_back(i);
else A.push_back(i);
}
int st = max(A.back(), (B.empty() ? -1 : B.back()));
st++;
if(st == n) return A.size();
int typ = (A.size() >= (n+sqr-1)/sqr ? 0 : 1);
int res = A.size();
for(int i = st;i < min(n, st+sqr);i++){
vector <int> query;
int x = i;
int con = 0;
while(x < n){
query.push_back((typ == 0 ? A[(x-st)/(sqr)] : B[(x-st)/(sqr)]));
query.push_back(x);
con += 2;
x += sqr;
}
query.push_back((typ == 0 ? A.back() : B.back()));
res += (typ == 0 ? (con-use_machine(query))/2 : use_machine(query)/2);
}
return res;
}
