#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
int get_ans(int sz, int ans, int x){
if(x == 0) return sz / 2 - (ans + 1) / 2;
return (ans + 1) / 2;
}
int count_mushrooms(int n){
int x = 0;
vector<int> pos[2];
int k = 80;
pos[x].push_back(0);
int tot = 1;
for(int i=1; i<n; i++){
vector<int> ask;
int sz = (int) pos[x].size();
for(int j=i; j<min(i + sz, n); j++){
ask.push_back(pos[x][j - i]);
ask.push_back(j);
}
i = min(i + sz, n) - 1;
int cur = use_machine(ask);
tot += get_ans((int) ask.size(), cur, x);
if(cur % 2 == 1){
pos[1 - x].push_back(i);
} else pos[x].push_back(i);
if((int) pos[1 - x].size() > (int) pos[x].size()) x = 1 - x;
}
return tot;
}
