#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';
vector<int> v;
v.pb(0);
v.pb(1);
int k=use_machine(v);
if(k==0)c[1]='A';
else c[1]='B';
if(n==2){
if(c[1]=='A')return 2;
return 1;
}
if(c[1]=='A'){
for(int i=3;i<n;i+=2){
v.clear();
v.pb(0);
v.pb(i-1);
v.pb(1);
v.pb(i);
k=use_machine(v);
boya(i-1,i,k,'A');
}
if(n%2){
v.clear();
v.pb(0);
v.pb(n-1);
k=use_machine(v);
if(k)c[n-1]='B';
else c[n-1]='A';
}
cev=0;
for(int i=0;i<n;i++){
if(c[i]=='A')cev++;
}
return cev;
}
v.clear();
v.pb(0);
v.pb(2);
k=use_machine(v);
if(k==0)c[2]='A';
else c[2]='B';
if(c[2]=='A'){
for(int i=4;i<n;i+=2){
v.clear();
v.pb(0);
v.pb(i-1);
v.pb(2);
v.pb(i);
k=use_machine(v);
boya(i-1,i,k,'A');
}
if(n%2==0){
v.clear();
v.pb(0);
v.pb(n-1);
k=use_machine(v);
if(k)c[n-1]='B';
else c[n-1]='A';
}
cev=0;
for(int i=0;i<n;i++){
if(c[i]=='A')cev++;
}
return cev;
}
for(int i=4;i<n;i+=2){
v.clear();
v.pb(1);
v.pb(i-1);
v.pb(2);
v.pb(i);
k=use_machine(v);
boya(i-1,i,k,'B');
}
if(n%2==0){
v.clear();
v.pb(1);
v.pb(n-1);
k=use_machine(v);
if(k)c[n-1]='A';
else c[n-1]='B';
}
cev=0;
for(int i=0;i<n;i++){
if(c[i]=='A')cev++;
}
return cev;
}
