#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi20/d2/debug.h"
#else
#define debug(...) void(37)
#endif
const int K = 72;
int count_mushrooms(int N) {
debug(N);
array<vector<int>, 2> sets;
sets[0].push_back(0);
int next = 1;
while (max(sets[0].size(), sets[1].size()) < K && next < N) {
int use = (sets[0].size() > sets[1].size() ? 0 : 1);
debug(use, sets[use]);
if (int(sets[use].size()) == 1 || next + 1 == N) {
sets[use ^ (use_machine({sets[use][0], next}))].push_back(next);
++next;
} else {
int res = use_machine({sets[use][0], next, sets[use][1], next + 1}); //bounds
sets[use ^ (res / 2)].push_back(next);
sets[use ^ (res % 2)].push_back(next + 1);
next += 2;
}
}
debug(sets);
array<int, 2> ct{};
while (next < N) {
int use = (sets[0].size() > sets[1].size() ? 0 : 1);
int s = int(sets[use].size());
int r = min(N, (next + s));
int tot = r - next;
vector<int> ask;
for (int i = 0; i < tot; ++i) {
ask.push_back(next + i);
ask.push_back(sets[use][i]);
}
int res = use_machine(ask);
int diff = (1 + res) / 2;
ct[use ^ 1] += diff;
ct[use] += tot - diff;
sets[use ^ (res % 2)].push_back(next);
next = r;
}
debug(sets, ct);
return int(sets[0].size()) + ct[0];
}
