#include "mushrooms.h"
#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int randint(int l,int r){
return uniform_int_distribution < int > (l,r) (rng);
}
///shuffle(a.begin(), a.end(), rng)
//#define int long long
const int MAX=1e6+4,inf=1e9,M2=5e5+3;
void maxx(int &a,int b){if(b>a) a=b;}
void minn(int &a,int b){if(b<a) a=b;}
template <class X, class Y>
bool cmin(X &a, const Y &b) {
return a > b ? a = b, 1 : 0;
}
bool cmax(int &a,int b){
if(b>a){a=b;return 1;} else return 0;
}
typedef pair < int, int > ii;
vector < int > pr[MAX];
struct qb{
int a,b;
int c;
qb(int a,int b,int c): a(a),b(b),c(c) {};
};
///g++ mushrooms.cpp stub.cpp -std=c++14 -O2
int count_mushrooms(int n) {
vector<int> vec,v0,v1;
v0.pb(0);
int cn=0,ans=1;
while(cn!=n-1){
vec.clear();
int dem=0;
if(v0.size()>v1.size()){
for(int u:v0)if(cn<n-1){
vec.pb(u);
vec.pb(++cn);dem++;
}
int x=use_machine(vec);
ans+=(dem-1-x/2);
if(x&1)v1.pb(cn);
else {
v0.pb(cn);
ans++;
}
}
else{
/*for(int u:v0){
vec.pb(u);
if(cn<n-1 && u!=v0.back())vec.pb(++cn);
}*/
for(int u:v1)if(cn<n-1){
vec.pb(u);
vec.pb(++cn);dem++;
}
int x=use_machine(vec);
ans+=x/2;
if(x&1){
v0.pb(cn);ans++;
}
else v1.pb(cn);
}
}
return ans;
}
