#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n){
vector <int> a,b;
a.push_back(0);
int ans=1,ptr=1;
while (ptr<n){
if (a.size()>=b.size()){
int s=max(0,min((int)a.size(),n-ptr-1)-1);
vector <int> ask;
for (int i=0; i<s; i++){
ask.push_back(a[i]);
ask.push_back(ptr); ptr++;
}
ask.push_back(a[s]);
ask.push_back(ptr); ptr++;
int ret=use_machine(ask);
ans+=(ask.size()-ret)/2;
if (ret%2==0) a.push_back(ptr-1);
else b.push_back(ptr-1);
} else {
int s=max(0,min((int)b.size(),n-ptr-1)-1);
vector <int> ask;
for (int i=0; i<s; i++){
ask.push_back(b[i]);
ask.push_back(ptr); ptr++;
}
ask.push_back(b[s]);
ask.push_back(ptr); ptr++;
int ret=use_machine(ask);
ans+=(ret+1)/2;
if (ret%2==1) a.push_back(ptr-1);
else b.push_back(ptr-1);
}
}
return ans;
}
