#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define vll vector<ll>
#define pll pair<ll, ll>
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef int ll;
const ll B=100;
int count_mushrooms(int n) {
ll cnt[2]={};
ll ans[2]={};
vll dumb(n-1);
for(ll i=0;i<n-1;i++){
dumb[i]=i+1;
}
shuffle(dumb.begin(), dumb.end(), rng);
vll ord;
ord.pb(0);
for(auto &it:dumb){
ord.pb(it);
}
array<vll, 2> v;
v[0].pb(0);
cnt[0]++;
ans[0]++;
for(ll i=1;i<n && i<2*B;i++){
vll tep;
tep.pb(0);
tep.pb(ord[i]);
ll re=use_machine(tep);
cnt[re]++;
ans[re]++;
v[re].pb(ord[i]);
}
if(2*B>=n){
return cnt[0];
}
if(cnt[0]>=cnt[1]){
ll pt=2*B;
while(pt<n){
vll tep;
ll cur=0;
for(ll rep=0;rep<cnt[0];rep++){
tep.pb(v[0][rep]);
if(pt<n){
tep.pb(ord[pt]);
pt++;
cur++;
}
}
ll re=use_machine(tep);
ll tep2=(re+1)/2;
ans[1]+=tep2;
ans[0]+=cur-tep2;
}
return ans[0];
}
else{
ll pt=2*B;
while(pt<n){
vll tep;
ll cur=0;
for(ll rep=0;rep<cnt[1];rep++){
tep.pb(v[1][rep]);
if(pt<n){
tep.pb(ord[pt]);
pt++;
cur++;
}
}
ll re=use_machine(tep);
ll tep2=(re+1)/2;
ans[0]+=tep2;
ans[1]+=cur-tep2;
}
return ans[0];
}
}
