#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;
char c[li];
int cev;
inline void boya(int i,int j,int k,char cc){
char cc1;
if(cc=='A')cc1='B';
else cc1='A';
if(k==0){c[i]=cc;c[j]=cc;}
if(k==1){c[i]=cc;c[j]=cc1;}
if(k==2){c[i]=cc1;c[j]=cc;}
if(k==3){c[i]=cc1;c[j]=cc1;}
}
int count_mushrooms(int n){
if(n==1)return 1;
c[0]='A';
cev=1;
vector<int> v,A,B;
A.pb(0);
for(int i=1;i<n;){
v.clear();
v.pb(i++);
if((int)A.size()>=(int)B.size()){
int siz=(int)A.size();
int say=0;
for(auto go:A){
v.pb(go);
say++;
if(say==siz || i>=n)break;
v.pb(i++);
}
int k=use_machine(v);
if(k%2){B.pb(v[0]);k--;}
else{A.pb(v[0]);cev++;}
say--;
say*=2;
say-=k;
cev+=say/2;
if((int)v.size()==4){
if(k)B.pb(v[2]);
else A.pb(v[2]);
}
}
else{
int siz=(int)B.size();
int say=0;
//~ cout<<i<<endl;
for(auto go:B){
v.pb(go);
say++;
if(say==siz || i>=n)break;
v.pb(i++);
}
int k=use_machine(v);
if(k%2){A.pb(v[0]);cev++;k--;}
else{B.pb(v[0]);}
if((int)v.size()==4){
if(k)A.pb(v[2]);
else B.pb(v[2]);
}
cev+=k/2;
}
}
return cev;
}
