#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define all(a) (a.begin(), a.end())
int N;
int sm=0;
vector<int> a;
vector<int> b;
const int MXSTOP=150;
void A();
void B();
void fase2(int st){
if(sz(a)>=sz(b)){
int j=1;
for (int i = st; i < N; i++)
{
a[j]=i;
j+=2;
if(j>=sz(a)) {
sm+=sz(a)/2-use_machine(a)/2;
j=1;
}
}
if(j>1) {
a.resize(j);
sm+=sz(a)/2-use_machine(a)/2;
}
}else{
int j=1;
for (int i = st; i < N; i++)
{
b[j]=i;
j+=2;
if(j>=sz(b)) {
sm+=use_machine(b)/2;
j=1;
}
}
if(j>1) {
b.resize(j);
sm+=use_machine(b)/2;
}
}
}
void A(int st){
sm+=2;
for (int j = st; j+1 < N; j+=2)
{
if(max(sz(a),sz(b))>MXSTOP*2) {
fase2(j);
return;
}
int um=use_machine({0,j,st-1,j+1});
if(um==0) {
a.push_back(-1);
a.push_back(j);
a.push_back(-1);
a.push_back(j+1);
}else if(um==1) {
a.push_back(-1);
a.push_back(j);
if(sz(b)>0) b.push_back(-1);
b.push_back(j+1);
}else if(um==2){
if(sz(b)>0) b.push_back(-1);
b.push_back(j);
a.push_back(-1);
a.push_back(j+1);
}else{
if(sz(b)>0) b.push_back(-1);
b.push_back(j);
b.push_back(-1);
b.push_back(j+1);
}
sm+=2-(um+1)/2;
}
if(st%2==(N-1)%2) sm+=1-use_machine({0,(int)N-1});
}
void B(int st){
sm+=1;
for (int j = st; j+1 < N; j+=2)
{
if(max(sz(a),sz(b))>MXSTOP*2) {
fase2(j);
return;
}
int um=use_machine({1,j,st-1,j+1});
if(um==0) {
b.push_back(-1);
b.push_back(j);
b.push_back(-1);
b.push_back(j+1);
}else if(um==1) {
b.push_back(-1);
b.push_back(j);
a.push_back(-1);
a.push_back(j+1);
}else if(um==2){
a.push_back(-1);
a.push_back(j);
b.push_back(-1);
b.push_back(j+1);
}else{
a.push_back(-1);
a.push_back(j);
a.push_back(-1);
a.push_back(j+1);
}
sm+=(um+1)/2;
}
if(st%2==(N-1)%2) sm+=1-use_machine({0,(int)N-1});
}
int count_mushrooms(int n) {
N=n;
sm=0;
a.clear();
b.clear();
a.push_back(0);
if(use_machine({0,1})==0) {
a.push_back(-1);
a.push_back(1);
A(2);
}
else{
b.push_back(1);
if(n==2) sm=1;
else{
if(use_machine({0,2})==0) {
a.push_back(-1);
a.push_back(2);
A(3);
}
else{
b.push_back(-1);
b.push_back(2);
B(3);
}
}
}
return sm;
}
