#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "mushrooms.h"
using namespace std;
template<typename X,typename Y> bool ckmin(X& x,Y y){return (x>y?x=y,1:0);}
using ii = pair<int,int>;
int use_machine(vector<int> x);
int count_mushrooms(int n){
vector<int>m;
vector<vector<int>>v(2,vector<int>());
int k = (n<=500?100:88), x, y, type = 0;
if(n<=226){
int ans = 1;
for(int i=1;i<n;++i)ans += (1 - use_machine({0,i}));
return ans;
}
v[0].pb(0);
int r1 = use_machine({0,1}), r2 = use_machine({0,2});
if(r1)v[1].pb(1);
else v[0].pb(1);
if(r2)v[1].pb(2);
else v[0].pb(2);
if(!r1)x = 0, y = 1;
else if(!r2)x = 0, y = 2;
else x = 1, y = 2, type = 1;
for(int i=3;i<2*k-1;i+=2){
assert(i+1<n);
int cur = use_machine({i,x,i+1,y});
if(cur&1)v[type^1].pb(i);
else v[type].pb(i);
if(cur>=2)v[type^1].pb(i+1);
else v[type].pb(i+1);
}
//deve dar uns 80 pontos
int target = (sz(v[0])>=k?0:1), ans = sz(v[0]);
for(int i=2*k-1;i<n;i+=k){
if(sz(v[target^1])>sz(v[target]))target ^= 1;
k = sz(v[target]);
vector<int>ask;
for(int j=0;j<k&&i+j<n;++j){
ask.pb(i+j), ask.pb(v[target][j]);
}
int cur = use_machine(ask);
if(cur&1)v[target^1].pb(i);
else v[target].pb(i);
if(target==1)ans += (cur+1)/2;
else ans += min(n-i,k) - (cur+1)/2;
}
return ans;
}
