#include "mushrooms.h"
//#define local
#ifndef local
//#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
///#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
vector<int> mp[10];
void prep(){
for(int i = 0; i < (1LL << 9); i++){
vector<int> v;
for(int j = 0; j < 9; j++) v.pb((i & (1LL << j)) != 0);
if(!v[0] || !v[2] || v[3] || v[5] || v[7]) continue;
if(v[1] == v[4]) continue;
int tot = 0;
for(int j = 0; j < 8; j++) tot += (v[j] != v[j + 1]);
//assert(!mp[tot].size());
//cout << tot << "\n";
//for(int j = 0; j < 9; j++) cout << v[j] << " ";
//cout << "\n";
mp[tot] = v;
}
//for(int i = 1; i <= 8; i++) assert(mp[i].size());
}
int count_mushrooms(int n){
if(n <= 200){
int answer = 1;
for(int i = 1; i < n; i++){
vector<int> v;
v.pb(0), v.pb(i);
answer += (!use_machine(v));
}
return answer;
}
int lim = min(n / 3, 120);
prep();
vector<int> v;
v.pb(0), v.pb(1);
vector<int> v1, v2;
v1.pb(0);
if(use_machine(v)) v2.pb(1);
else v1.pb(1);
v.clear();
v.pb(0), v.pb(2);
if(use_machine(v)) v2.pb(2);
else v1.pb(2);
int itr = 2;
while(v1.size() < lim && v2.size() < lim){
vector<int> v;
if(v1.size() >= 2){
v.pb(v1[0]), v.pb(itr + 1), v.pb(v1[1]), v.pb(itr + 2);
int temp = use_machine(v);
if(temp & 1) v2.pb(itr + 2);
else v1.pb(itr + 2);
if(temp & 2) v2.pb(itr + 1);
else v1.pb(itr + 1);
}
else{
v.pb(v2[0]), v.pb(itr + 1), v.pb(v2[1]), v.pb(itr + 2);
int temp = use_machine(v);
if(temp & 1) v1.pb(itr + 2);
else v2.pb(itr + 2);
if(temp & 2) v1.pb(itr + 1);
else v2.pb(itr + 1);
}
itr += 2;
if(v1.size() >= 3 && v2.size() >= 3) break;
}
itr++;
//cout << itr << " " << v1.size() << " " << v2.size() << "\n";
while(v1.size() < lim && v2.size() < lim){
vector<int> v;
v.pb(v1[0]);
v.pb(itr);
v.pb(v1[1]);
v.pb(itr + 1);
v.pb(v1[2]);
v.pb(itr + 2);
int temp = use_machine(v);
//cout << temp << " " << v1.size() << " " << v2.size() << " " << "\n";
if(temp <= 1){
v1.pb(itr), v1.pb(itr + 1);
if(temp == 1) v2.pb(itr + 2);
else v1.pb(itr + 2);
itr += 3;
continue;
}
if(temp >= 4){
v2.pb(itr), v2.pb(itr + 1);
if(temp == 4) v1.pb(itr + 2);
else v2.pb(itr + 2);
itr += 3;
continue;
}
if(temp == 2) v1.pb(itr + 2);
else v2.pb(itr + 2);
v.clear();
v.pb(v2[0]), v.pb(itr), v.pb(v2[1]), v.pb(v1[0]), v.pb(itr + 1), v.pb(v1[1]), v.pb(itr + 3), v.pb(v1[2]), v.pb(itr + 4);
temp = use_machine(v);
vector<int> vv = mp[temp];
if(!vv[1]) v1.pb(itr);
else v2.pb(itr);
if(!vv[4]) v1.pb(itr + 1);
else v2.pb(itr + 1);
if(!vv[6]) v1.pb(itr + 3);
else v2.pb(itr + 3);
if(!vv[8]) v1.pb(itr + 4);
else v2.pb(itr + 4);
itr += 5;
//cout << itr << " " << v1.size() << " " << v2.size() << "\n";
}
//itr++;
int answer = v1.size();
//return answer;
while(itr < n){
if(v1.size() >= v2.size()){
int nxt = min(n - 2, itr + (int)v1.size() - 2);
vector<int> v;
for(int i = itr; i <= nxt; i++){
v.pb(v1[i - itr]), v.pb(i);
}
assert((nxt - itr + 1) < v1.size());
v.pb(v1[nxt - itr + 1]);
v.pb(nxt + 1);
int temp = use_machine(v);
answer += (v.size() - 1 - temp)/2;
if(temp & 1) v2.pb(nxt + 1);
else{
v1.pb(nxt + 1);
answer++;
}
itr = nxt + 2;
//cout << answer << "\n";
}
else{
int nxt = min(n - 2, itr + (int)v2.size() - 2);
vector<int> v;
for(int i = itr; i <= nxt; i++){
v.pb(v2[i - itr]), v.pb(i);
}
assert((nxt - itr + 1) < v2.size());
v.pb(v2[nxt - itr + 1]);
v.pb(nxt + 1);
int temp = use_machine(v);
answer += temp/2;
if(temp & 1){
v1.pb(nxt + 1);
answer++;
}
else v2.pb(nxt + 1);
itr = nxt + 2;
}
}
return answer;
}
