#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define vec vector
int n;
vec<int> a, b;
int nx;
int a_ex, b_ex;
int qry(vec<int> x) {
vec<int> y;
for (int z : x)
y.push_back(z - 1);
return use_machine(y);
}
void inc1() {
int nm = qry({1, nx});
if (nm == 0) a.push_back(nx);
else b.push_back(nx);
nx++;
}
bool on(int x, int i) { return x & (1 << i); }
void inc2() {
if (a.size() >= 2) {
int nm = qry({nx, a[0], nx + 1, a[1]});
if (on(nm, 0)) b.push_back(nx);
else a.push_back(nx);
if (on(nm, 1)) b.push_back(nx + 1);
else a.push_back(nx + 1);
nx += 2;
} else {
int nm = qry({nx, b[0], nx + 1, b[1]});
if (on(nm, 0)) a.push_back(nx);
else b.push_back(nx);
if (on(nm, 1)) a.push_back(nx + 1);
else b.push_back(nx + 1);
nx += 2;
}
}
void inc3() {
if (a.size() >= b.size()) {
int sz = min((int) a.size(), n - nx + 1);
vec<int> qr;
for (int i = 0; i < 2 * sz; i++) {
if (i % 2 == 0) qr.push_back(nx + i / 2);
else qr.push_back(a[i / 2]);
}
int nm = qry(qr);
if (on(nm, 0)) b.push_back(nx);
else a.push_back(nx);
b_ex += nm / 2, a_ex += (sz - 1 - nm / 2);
nx += sz;
} else {
int sz = min((int) b.size(), n - nx + 1);
vec<int> qr;
for (int i = 0; i < 2 * sz; i++) {
if (i % 2 == 0) qr.push_back(nx + i / 2);
else qr.push_back(b[i / 2]);
}
int nm = qry(qr);
if (on(nm, 0)) a.push_back(nx);
else b.push_back(nx);
a_ex += nm / 2, b_ex += (sz - 1 - nm / 2);
nx += sz;
}
}
int count_mushrooms(int _n) {
n = _n, a = {1}, b = {}, nx = 2, a_ex = 0, b_ex = 0;
if (n <= 226) {
while (nx <= n)
inc1();
return a.size();
}
while (max(a.size(), b.size()) <= 1)
inc1();
while (max(a.size(), b.size()) <= 90)
inc2();
while (nx <= n)
inc3();
return a.size() + a_ex;
}
