#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 140;
int count_mushrooms(int n) {
if (n <= 226) {
int cnt = 0;
for (int i = 1; i < n; i++) {
if (use_machine({0, i})) continue;
cnt++;
}
return cnt+1;
}
vector<int> as, bs; as.push_back(0);
int a = use_machine({0, 1}), b = use_machine({0, 2});
int c, d, flp = 0;
if (!a && !b) {
c = 0, d = 1;
as.push_back(1);
as.push_back(2);
} else if (a && b) {
c = 1, d = 2; flp = 1;
bs.push_back(1);
bs.push_back(2);
} else {
if (a) {
c = 0;
d = 2;
bs.push_back(1);
as.push_back(2);
} else {
c = 1;
d = 2;
bs.push_back(2);
as.push_back(1);
}
}
int ans = 1 + (1 - a) + (1 - b);
int iter = min(n, M*2);
for (int i = 3; i < iter; i += 2) {
if (i >= iter) return ans;
vector<int> query;
query.push_back(c); query.push_back(i); query.push_back(d);
if (i < iter - 1) {
query.push_back(i + 1);
}
int k = use_machine(query);
if (k == 0) {
if (!flp) {
ans++;
as.push_back(i);
if (i < iter - 1) {
ans++;
as.push_back(i + 1);
}
} else {
bs.push_back(i);
if (i < iter - 1) bs.push_back(i + 1);
}
} else if (k == 1) {
if (!flp) bs.push_back(i + 1);
else {
as.push_back(i + 1);
ans++;
}
} else if (k == 2) {
if (!flp) bs.push_back(i);
else {
as.push_back(i);
ans++;
}
} else {
assert(k == 3);
if (!flp) {
bs.push_back(i + 1);
bs.push_back(i);
}
else {
as.push_back(i + 1);
as.push_back(i);
ans += 2;
}
}
}
vector<int> ps; bool flp2 = false;
if (as.size() > bs.size()) for (auto &x : as) ps.push_back(x);
else {
flp2 = true;
for (auto &x : bs) ps.push_back(x);
}
int c2 = 0;
int blksize = ps.size() - 1;
for (int i = iter; i < n; i += blksize) {
vector<int> qrs;
for (int j = 0; j < blksize; j++) {
if (i+j >= n) break;
qrs.push_back(ps[j]);
qrs.push_back(i+j);
}
qrs.push_back(ps.back());
int k = use_machine(qrs);
if (flp2) c2 += k/2;
else {
int used = ((int)qrs.size()-1)/2;
c2 += used - k/2;
}
if ((int)qrs.size() < 2*blksize+1) break;
}
return (int)as.size() + c2;
}
