#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
const ll maxn = 1e5+5;
const int bloc = 95;
int count_mushrooms(int n) {
int ret;
vector<int> A, B;
A.pb(0);
int ptr = 1;
while(ptr < n){
vector<int> tp = {0, ptr};
ret = use_machine(tp);
if (ret == 0) A.pb(ptr);
else B.pb(ptr);
ptr++;
if (SZ(A) >= bloc || SZ(B) >= bloc) break;
}
if (ptr == n){
return SZ(A);
}
int cnt = 0;
while(ptr < n){
vector<int> tmp;
REP(i, bloc){
if (ptr == n) break;
if (SZ(A) >= bloc) tmp.pb(A[i]);
else tmp.pb(B[i]);
tmp.pb(ptr);
ptr++;
}
ret = use_machine(tmp);
if (SZ(A) >= bloc){
cnt += 1-(ret&1);
ret /= 2;
cnt += (SZ(tmp)/2-1 - ret);
}
else{
cnt += (ret&1);
ret/=2;
cnt += ret;
}
}
return cnt + SZ(A);
}
