#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
#define endl "\n"
typedef long long int ll;
const int MOD = 1e9 + 7;
int use_machine(vector<int> x);
int count_mushrooms(int n){
//Initially ask 73 questions.
vector<int> a = {0};
vector<int> b;
int ans = 1;
int rep = use_machine({0, 1});
if(rep == 1){
b.push_back(1);
}else {a.push_back(1); ans++;}
if(n == 2) return ans;
rep = use_machine({0, 2});
if(rep == 1){
b.push_back(2);
}else {a.push_back(2); ans++;}
int left = 72;
int curr = 3;
while(left > 0 && curr < n){
if(curr == n - 1){
rep = use_machine({0, curr});
if(rep == 0) ans++;
return ans;
}
if((int)a.size() >= 2){
rep = use_machine({0, curr, a[1], curr + 1});
if(rep >= 2) b.push_back(curr);
else {a.push_back(curr); ans++;}
if(rep % 2 == 1) b.push_back(curr + 1);
else {a.push_back(curr + 1); ans++;}
}
curr += 2;
left--;
}
while(curr < n){
if((int)a.size() < (int)b.size()){
vector<int> v;
for(int x : b){
v.push_back(x);
v.push_back(curr);
curr++;
if(curr == n) break;
}
rep = use_machine(v);
ans += rep / 2;
if(rep % 2 == 1) ans++;
}else{
vector<int> v;
int asked = 0;
for(int x : b){
v.push_back(x);
v.push_back(curr);
curr++;
asked++;
if(curr == n) break;
}
rep = use_machine(v);
ans += asked - rep / 2;
if(rep % 2 == 1) ans--;
}
}
return ans;
}
