#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define m_p make_pair
typedef long long ll;
mt19937 rnf(234);
const int M = 200;
int count_mushrooms(int n)
{
vector<int> v;
for (int i = 1; i < min(n, M); ++i)
v.push_back(i);
vector<int> a;
vector<int> b;
a.push_back(0);
while (!v.empty())
{
if (sz(v) == 1)
{
int q = use_machine({0, v[0]});
if (q == 0)
a.push_back(v[0]);
else
b.push_back(v[0]);
v.pop_back();
break;
}
int x = v.back();
v.pop_back();
int y = v.back();
v.pop_back();
int q = use_machine({0, x, y});
if (q == 0)
{
a.push_back(x);
a.push_back(y);
}
else if (q == 2)
{
b.push_back(x);
a.push_back(y);
}
else
{
b.push_back(y);
v.push_back(x);
}
}
int ans = sz(a);
for (int i = M; i < n; ++i)
v.push_back(i);
if (sz(a) > sz(b))
{
while (!v.empty())
{
if (sz(v) < sz(a))
{
vector<int> x;
x.push_back(a[0]);
for (int i = 0; i < sz(v); ++i)
{
x.push_back(v[i]);
x.push_back(a[i + 1]);
}
ans += (sz(v) - use_machine(x) / 2);
v.clear();
}
else
{
vector<int> u;
for (int i = 0; i < sz(a) - 1; ++i)
{
u.push_back(v.back());
v.pop_back();
}
vector<int> x;
x.push_back(a[0]);
for (int i = 0; i < sz(u); ++i)
{
x.push_back(u[i]);
x.push_back(a[i + 1]);
}
ans += (sz(u) - use_machine(x) / 2);
u.clear();
}
}
}
else
{
while (!v.empty())
{
if (sz(v) < sz(b))
{
vector<int> x;
x.push_back(b[0]);
for (int i = 0; i < sz(v); ++i)
{
x.push_back(v[i]);
x.push_back(b[i + 1]);
}
ans += use_machine(x) / 2;
v.clear();
}
else
{
vector<int> u;
for (int i = 0; i < sz(b) - 1; ++i)
{
u.push_back(v.back());
v.pop_back();
}
vector<int> x;
x.push_back(b[0]);
for (int i = 0; i < sz(u); ++i)
{
x.push_back(u[i]);
x.push_back(b[i + 1]);
}
ans += use_machine(x) / 2;
u.clear();
}
}
}
return ans;
}
