#include <bits/stdc++.h>
using namespace std;
int use_machine(vector<int> x);
const int SQRT = 90;
int strat1(int n){
vector<bool> type(n);
{
int t = use_machine({0,1});
if(t==0)type[1]=false;
else type[1]=true;
}
if(n>2){
int t = use_machine({0,2});
if(t==0)type[2]=false;
else type[2]=true;
} else {
return 1 + (int)(type[1]==false);
}
int a,b;bool ty;
if(type[0]==type[1]){
a = 0;
b = 1;
ty = false;
} else if(type[0]==type[2]){
a = 0;
b = 2;
ty = false;
} else {
a = 1;
b = 2;
ty = true;
}
type.emplace_back(false);
for(int i=3;i<n;i+=2){
int curr;
if(i==n-1){
curr = use_machine({a,i,b});
} else {
curr = use_machine({a,i,b,i+1});
}
if(curr&1){
type[i+1] = !ty;
} else type[i+1] = ty;
if(curr&2){
type[i] = !ty;
} else type[i] = ty;
}
int ans = 0;
for(int i=0;i<n;i++)if(type[i]==false)ans++;
return ans;
}
pair<vector<int>,vector<int>> ask(){
vector<bool> type(3*SQRT);
int cnt_false = 1,cnt_true = 0;
{
int t = use_machine({0,1});
if(t==0){type[1]=false;cnt_false++;}
else {type[1]=true;cnt_true++;}
}
{
int t = use_machine({0,2});
if(t==0){type[2]=false;cnt_false++;}
else {type[2]=true;cnt_true++;}
}
int a,b;bool ty;
if(type[0]==type[1]){
a = 0;
b = 1;
ty = false;
} else if(type[0]==type[2]){
a = 0;
b = 2;
ty = false;
} else {
a = 1;
b = 2;
ty = true;
}
type.emplace_back(false);
vector<int> falses;
vector<int> trues;
for(int i=3;i<2*SQRT-1;i+=2){
int curr = use_machine({a,i,b,i+1});
if(curr&2){
type[i] = !ty;
} else type[i] = ty;
if(curr&1){
type[i+1] = !ty;
} else type[i+1] = ty;
}
for(int i=0;i<2*SQRT-1;i++)if(type[i])trues.emplace_back(i);
for(int i=0;i<2*SQRT-1;i++)if(!type[i])falses.emplace_back(i);
return {falses,trues};
}
int count_mushrooms(int n) {
if(n<=450)return strat1(n);
auto [falses,trues] = ask();
int ans = falses.size();
for(int i=2*SQRT-1;i<n;){
vector<int> buffer;
int siz = max(falses.size(),trues.size());
for(int j=0;j<siz;j++)if(i+j<n)buffer.emplace_back(i+j);
i+=siz;
vector<int> query;
query.emplace_back(buffer.front());
auto iter = buffer.begin()+1;
bool type;
if(falses.size()<trues.size())type = true;
else type = false;
auto iterb = trues.begin();
if(type)iterb = trues.begin();
else iterb = falses.begin();
while(iter!=buffer.end()){
query.emplace_back(*iterb++);
query.emplace_back(*iter++);
}
query.emplace_back(*iterb++);
if(type){
int t = use_machine(query);
if(t&1)falses.emplace_back(query.front());
else trues.emplace_back(query.front());
t++;t/=2;
ans+=t;
} else {
int t = use_machine(query);
if(t&1)trues.emplace_back(query.front());
else falses.emplace_back(query.front());
t++;t/=2;
ans+=buffer.size()-t;
}
}
return ans;
}
