#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
class Solver{
private:
ll n;
vi type, ctr;
vvi byType;
void add_type(ll x, bool t){
if (n <= x || type[x] != -1) return;
type[x] = t;
byType[t].push_back(x);
ctr[t]++;
}
void addOne(ll x){
ll res = use_machine(vi{0,x});
add_type(x,res);
}
void addTwo(ll x, ll y){
//cout << x << " " << y << endl;
bool t = 0;
if (byType[0].size() < 2){
t = 1;
}
//cout << t << " " << byType[t].size() << endl;
ll res = use_machine(vi{x,byType[t][0],y,byType[t][1]});
add_type(x,(res&1) ? !t : t);
add_type(y,(res&2) ? !t : t);
}
bool big_query (){
bool t = ((byType[0].size() > byType[1].size()) ? 0 : 1);
ll min_idx = ctr[0]+ctr[1];
ll max_idx = min((int)min_idx + (int)byType[t].size()-1,n-1);
ll sz = max_idx-min_idx+1;
if (min_idx >= n) return false;
vi v;
for (ll i = min_idx; max_idx >= i && n > i; i++){
v.push_back(i);
v.push_back(byType[t][i-min_idx]);
}
/*
cout << min_idx << " - " << max_idx << endl;
for (auto i: v) cout << i << " ";
cout << endl;
*/
ll res = use_machine(v);
if (res%2 == 1){
res--;
add_type(min_idx,!t);
}else add_type(min_idx,t);
ctr[!t] += res/2;
ctr[t] += sz-1-res/2;
return true;
}
public:
Solver(ll n): n(n), type(n,-1), ctr(2,0), byType(2){
type[0] = 0;
ctr[0]++;
byType[0].push_back(0);
}
int solve(){
//cout << "hello\n";
addOne(1);
if (n > 2){
addOne(2);
for (ll i = 0; 80 > i && n > 2*i+4; i++){
addTwo(2*i+3,2*i+4);
}
//cout << "hello\n";
while(big_query()){}
}
return ctr[0];
}
};
int count_mushrooms(int n) {
Solver mySolver(n);
return mySolver.solve();
}
