#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int use_machine(std::vector<int> x);
int count_mushrooms(int n) {
int ans = 0;
if(n <= 200){
for(int i = 1; i < n; ++i){
vector<int> v {0, i};
ans += 1 - use_machine(v);
}
return ans + 1;
}
vector<int> a {0}, b; //specific zeros and ones
int S = 282, K = 0;
for(int i = 1; i < min(S + 2, n); i++){
vector<int> v {0, i};
int val = use_machine(v);
if(val==0){
a.pb(i);
}else{
b.pb(i);
}
K = i;
if(a.size() >= 2 || b.size() >= 2){
break;
}
}
for(int i = K + 1; i + 1 < min(S + 2, n); i += 2){
if(a.size() >= 2){
vector<int> v {a[0], i, a[1], i + 1};
int val = use_machine(v);
if(val == 0){
a.pb(i);
a.pb(i+1);
}else if(val == 1){
a.pb(i);
b.pb(i+1);
}else if(val == 2){
b.pb(i);
a.pb(i+1);
}else{
b.pb(i);
b.pb(i+1);
}
}else{
vector<int> v {b[0], i, b[1], i + 1};
int val = use_machine(v);
if(val == 0){
b.pb(i);
b.pb(i+1);
}else if(val == 1){
b.pb(i);
a.pb(i+1);
}else if(val == 2){
a.pb(i);
b.pb(i+1);
}else{
a.pb(i);
a.pb(i+1);
}
}
K = i + 1;
}
if(a.size() < b.size()){
S = b.size();
S--;
for(int i = K + 1; i + S <= n; i += S){
vector<int> v;
int ind = 0;
for(int j = i; j < i + S; ++j){
v.pb(j), v.pb(b[ind++]);
K = j;
}
int val = use_machine(v);
ans += val/2 + (val%2);
}
if(K + 1 < n){
vector<int> v;
int ind = 0;
for(int j = K + 1; j < n; ++j){
v.pb(j), v.pb(b[ind++]);
}
int val = use_machine(v);
ans += val/2 + (val%2);
}
}else{
S = a.size();
S--;
// cout << S <<"S" << K << endl;;
for(int i = K + 1; i + S <= n; i += S){
vector<int> v;
int ind = 0;
for(int j = i; j < i + S; ++j){
v.pb(j), v.pb(a[ind++]);
K = j;
}
int val = use_machine(v);
ans += v.size()/2 - val/2 - (val%2);
}
if(K + 1 < n){
vector<int> v;
int ind = 0;
for(int j = K + 1; j < n; ++j){
v.pb(j), v.pb(a[ind++]);
}
int val = use_machine(v);
ans += v.size()/2 - val/2 - (val%2);
}
}
return ans + a.size();
}
