#include <bits/stdc++.h>
using namespace std;
int const N=20005;
int const H=100;
int use_machine(vector<int> x);
int count_mushrooms(int n){
vector<int> A,B;
A.push_back(0);
vector<int> q;
q.push_back(0);
for(int i=1;i<n;i++){
q.push_back(i);
if(use_machine(q))
B.push_back(i);
else
A.push_back(i);
q.pop_back();
if(A.size()>=100 || B.size()>=100)
break;
}
bool bl=0;
if(A.size()<B.size()){
swap(A,B);
bl=1;
}
int cntA=A.size(),cntB=B.size();
for(int i=(A.size()+B.size());i<n;i+=H){
vector<int> q;
for(int j=i;j<min(i+H,n);j++){
q.push_back(A[j-i]);
q.push_back(j);
}
int v=use_machine(q)+1;
cntB+=v/2;
}
cntA=n-cntB;
if(bl)
swap(cntB,cntA);
return cntA;
}
