#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int X=100;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int count_mushrooms(int n){
vector<int> ord;
for (int i=1; i<n; ++i)ord.pb(i);
vector<vector<int> > vect(2);
vect[0].pb(0);
if (n<=227){
int res=1;
for (int i=1; i<n; ++i)res+=!use_machine({0, i});
return res;
}
while (max(vect[0].size(), vect[1].size())<2){
if (use_machine({0, ord.back()}))vect[1].pb(ord.back());
else vect[0].pb(ord.back());
ord.pop_back();
}
while ((max(vect[0].size(), vect[1].size())<3||min(vect[0].size(), vect[1].size())<2)&&max(vect[0].size(), vect[1].size())<X){
int a=ord.back(), b=ord[ord.size()-2], id=0;
if (vect[1].size()>vect[0].size())id=1;
ord.pop_back(), ord.pop_back();
int res=use_machine({vect[id][0], a, vect[id][1], b});
if (res&1)vect[!id].pb(b);
else vect[id].pb(b);
if (res&2)vect[!id].pb(a);
else vect[id].pb(a);
}
while (max(vect[0].size(), vect[1].size())<X){
if (use_machine({0, ord.back()}))vect[1].pb(ord.back());
else vect[0].pb(ord.back());
ord.pop_back();
}
int ans=vect[0].size();
while (ord.size()){
int id=0;
if (vect[0].size()<vect[1].size())id=1;
vector<int> temp;
for (int i=0; i<vect[id].size()&&ord.size(); ++i)temp.pb(vect[id][i]), temp.pb(ord.back()), ord.pop_back();
int res=use_machine(temp);
if (id)ans+=res/2+res%2;
else ans+=temp.size()/2-(res/2+res%2);
if (res%2)vect[!id].pb(temp.back());
else vect[id].pb(temp.back());
}
return ans;
}
