#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
#define ll long long
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
int count_mushrooms(int n) {
vector<int> ids(n-1);
iota(all(ids),1);
reverse(all(ids));
vector<int> tipo[2];
tipo[0].clear();tipo[1].clear();
tipo[0].push_back(0);
vector<int> aux;
int resp=0;
vector<int> fila;
if(sz(ids)<100){
while(!ids.empty() && sz(tipo[0])<3 && sz(tipo[1])<3){
aux.clear();
aux.push_back(0);
aux.push_back(ids.back());
int v=use_machine(aux);
tipo[v].push_back(ids.back());
ids.pop_back();
}
}
else{
while(!ids.empty() && sz(tipo[0])<2 && sz(tipo[1])<2){
aux.clear();
aux.push_back(0);
aux.push_back(ids.back());
int v=use_machine(aux);
tipo[v].push_back(ids.back());
ids.pop_back();
}
int at=0;if(sz(tipo[1])==2)at=1;
while(!ids.empty() && sz(tipo[0])<3 && sz(tipo[1])<3){
aux.clear();
int a=ids.back();ids.pop_back();
int b=ids.back();ids.pop_back();
aux={tipo[at][0],a,tipo[at][1],b};
int v=use_machine(aux);
if(v&1)tipo[at^1].push_back(b);
else tipo[at].push_back(b);
if(v&2)tipo[at^1].push_back(a);
else tipo[at].push_back(a);
}
}
auto goat=[&](int at,int a, int b, int c, int d)->void{
aux.clear();aux={tipo[at^1][0],a,tipo[at^1][1],tipo[at][0],b,tipo[at][1],c,tipo[at][2],d};
int v=use_machine(aux);
v--;
if(v&1){
tipo[at^1].push_back(d);
}else{
tipo[at].push_back(d);
}
if(v&2){
tipo[at^1].push_back(c);
}
else tipo[at].push_back(c);
if(v&4){
tipo[at].push_back(a);
tipo[at^1].push_back(b);
}
else{
tipo[at].push_back(b);
tipo[at^1].push_back(a);
}
};
auto op=[&](int a,int b, int c, int at)->void{
aux.clear();
aux={tipo[at][0],a,tipo[at][1],b,tipo[at][2],c};
int v=use_machine(aux);
if(v&1){
tipo[at^1].push_back(c);
v--;
}
else tipo[at].push_back(c);
if(v==4){
tipo[at^1].push_back(a);
tipo[at^1].push_back(b);
}
else if(v==2){
if(sz(tipo[at^1])<2){
aux.clear();aux={0,a};v=use_machine(aux);
tipo[v].push_back(a);
tipo[v^1].push_back(b);
}else{
int d=ids.back();ids.pop_back();
int e=ids.back();ids.pop_back();
goat(at,a,b,d,e);
}
}
else{
tipo[at].push_back(a);
tipo[at].push_back(b);
}
};
int at=0;
if(sz(tipo[1])>=3)at=1;
int m=100;
while(sz(ids)>6 && sz(tipo[0])<m && sz(tipo[1])<m){
int a=ids.back();ids.pop_back();
int b=ids.back();ids.pop_back();
int c=ids.back();ids.pop_back();
op(a,b,c,at);
}
if(sz(ids)<=6){
while(sz(ids)>0){
int x=ids.back();
aux.clear();
aux={0,x};
int v=use_machine(aux);
tipo[v].push_back(x);
ids.pop_back();
}
}
if(sz(ids)==0){
return resp+sz(tipo[0]);
}
at=0;
if(sz(tipo[1])>=sz(tipo[0]))at=1;
while(!ids.empty()){
int vida=sz(tipo[at])-1;
aux.clear();
while(vida>=0 && !ids.empty()){
aux.push_back(tipo[at][vida]);
aux.push_back(ids.back());
ids.pop_back();
vida--;
}
int v=use_machine(aux);
int oposto=0;
if(v&1){
v++;
oposto=1;
}
if(at==1){
resp+=v/2;
if(oposto==1){
resp--;
tipo[0].push_back(aux.back());
}
else{
tipo[1].push_back(aux.back());
}
}
else{
resp+=sz(aux)/2-v/2;
if(oposto==1){
tipo[1].push_back(aux.back());
}
else{
tipo[0].push_back(aux.back());
resp--;
}
}
if(sz(tipo[at^1])>sz(tipo[at]))at^=1;
}
return resp+sz(tipo[0]);
}
