#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
#define in insert
int count_mushrooms(int n) {
ll ans = 1;
if(n <= 226){
for(ll i = 1; i < n; i++){
ans += 1 - use_machine({0, i});
}
return ans;
}
vector < ll > done(n + 100, 0);
vector < ll > A, B;
A.pb(0);
ll N = 200;
for(ll i = 1; i <= 2; i++){
if(1 - use_machine({0, i})) A.pb(i), ans++;
else B.pb(i), ans++;
}
for(ll i = 3; i <= N; i+=2){
if(A.size() > B.size()){
ll k = use_machine({A[0], i, A[1], i + 1});
if(k == 0) A.pb(i), A.pb(i + 1), ans+=2;
if(k == 1) A.pb(i), B.pb(i + 1), ans++;
if(k == 2) B.pb(i), A.pb(i + 1), ans++;
if(k == 3) B.pb(i), B.pb(i + 1);
}else{
ll k = use_machine({B[0], i, B[1], i + 1});
if(k == 3) A.pb(i), A.pb(i + 1), ans += 2;
if(k == 2) A.pb(i), B.pb(i + 1), ans++;
if(k == 1) B.pb(i), A.pb(i + 1), ans++;
if(k == 0) B.pb(i), B.pb(i + 1);
}
}
ll sz; bool f = 0;
if(B.size() > A.size()) f = 1, sz = B.size();
else sz = A.size();
for(ll i = N+1; i + sz - 1 < n; i+=sz){
if(!f){
vector < ll > cur;
cur.pb(A[0]); ll p = i, q = 0;
for(ll j = 1; j < sz; j++){
done[p] = 1;
cur.pb(p);
cur.pb(A[j]);
p++;
q++;
if(p == n) break;
}
ll k = use_machine(cur);
ans += (q) - (k/2);
}else{
vector < ll > cur;
cur.pb(B[0]); ll p = i, q = 0;
for(ll j = 1; j < sz; j++){
done[p] = 1;
cur.pb(p);
cur.pb(B[j]);
p++;
q++;
if(p == n) break;
}
ll k = use_machine(cur);
ans += (k/2);
}
}
return ans;
}
