#include "mushrooms.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 1e9;
int use_machine(std::vector<int> x);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int n) ;
int count_mushrooms(int n) {
int ans = 1;
vector<int> psa , psb;
psa.push_back(0);
int j = 1;
while(j < n){
vector<int> ps;
bool pa = true;
int msz = 0;
if(psa.size() >= psb.size()){
msz = psa.size();
for(auto to : psa) ps.push_back(to);
}
else{
pa = false;
msz = psb.size();
for(auto to : psb) ps.push_back(to);
}
int lps = j , c = 0;
vector<int> qu;
for(int i = j;i < min(n , j + msz); ++ i){
lps = i;
qu.push_back(ps[i - j]);
qu.push_back(i);
c ++;
}
j = min(n , j + msz);
//cout << c << ' ' << pa << '\n';
int k = use_machine(qu);
if(! pa){
ans += (k + 1) / 2;
if(k % 2 == 0) psb.push_back(lps);
else psa.push_back(lps);
}
else{
ans += (c - (k + 1) / 2);
if(k % 2 == 1) psb.push_back(lps);
else psa.push_back(lps);
}
}
return ans;
}
