#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define pb push_back
#define popb pop_back
#define all(x) (x).begin(),(x).end()
vi p, rnk, op;
int findset(int x){return p[x] = p[x] == x? x: findset(p[x]);}
void unite(int i, int j)
{
int x= findset(i);
int y = findset(j);
if(x == y)
return ;
if(rnk[x] > rnk[y])
swap(x,y);
p[x] = y;
if(rnk[x] == rnk[y])
rnk[y] ++ ;
}
void solve(int l, int r, int cnt)
{
if(l == r)
return ;
int m = (l + r)/2;
vi A, B;
for(int i = l; i <= m; i ++)
A.pb(i);
for(int i = m + 1; i <= r; i ++)
B.pb(i);
int a = m - l + 1 > 1? use_machine(A): 0;
int b = r - m > 1? use_machine(B): 0;
if( a + b == cnt)
unite(m, m + 1);
else
op[m] = 1;
solve(l, m, a);
solve(m + 1, r, b);
return ;
}
int count_mushrooms(int n)
{
p.resize(n);
rnk.assign(n,0);
op.assign(n, 0);
for(int i = 0 ; i < n; i++)
p[i] = i ;
vi perm;
for(int i= 0; i < n; i++)
perm.pb(i);
solve(0, n-1,use_machine(perm));
char c = 'A';
int ans = 0;
for(int i = 0 ; i < n; i++ )
{
if(c == 'A')
ans ++ ;
if(op[i])
c = c == 'A' ? 'B': 'A';
}
return ans;
}
/*
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
}
*/
