#include<bits/stdc++.h>
using namespace std;
int use_machine(vector<int> x);
int count_mushrooms(int n){
int checked=2;
if(n==2){
return 2-use_machine(vector<int>{0,1});
}
vector<int> A={0};
vector<int> B;
if(use_machine(vector<int>{0,1})==0){
A.push_back(1);
}
else{
checked=3;
B.push_back(1);
if(use_machine(vector<int>{0,2})==0){
A.push_back(2);
}
else{
B.push_back(2);
}
}
if (n<226){
for(int i=checked;i<n;i++){
if(use_machine(vector<int>{0,i})==0){
A.push_back(i);
}
}
return A.size();
}
for(;checked<220;checked+=2){
if(A.size()>1){
int val=use_machine(vector<int>{A[0],checked,A[1],checked+1});
if(val%2==0){
A.push_back(checked+1);
}
else{
B.push_back(checked+1);
}
if(val>1){
B.push_back(checked);
}
else{
A.push_back(checked);
}
}
else{
int val=use_machine(vector<int>{B[0],checked,B[1],checked+1});
if(val%2==0){
B.push_back(checked+1);
}
else{
A.push_back(checked+1);
}
if(val>1){
A.push_back(checked);
}
else{
B.push_back(checked);
}
}
}
//if(A.size()*3/2 > B.size() || B.size()*3/2 > A.size()){
bool inverse=false;
if(B.size()>A.size()){
inverse=true;
A=B;
}
int value=A.size();
bool running=true;
while(running){
vector<int> Question;
int inv=0;
for(int i=0;i<A.size();i++){
if(checked==n){
running=false;
}
else{
inv++;
Question.push_back(checked);
checked++;
}
Question.push_back(A[i]);
}
int val=use_machine(Question);
if(val>0){
val=((val-1)/2+1);
}
value+=inv-val;
}
if(inverse){
value=n-value;
}
return value;
//}
}
