#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
ll brutforce(ll n) {
ll ret = 1;
for (ll i = 1; i + 1 < n; i += 2)
ret += 2 - use_machine({i, 0, i + 1});
if (n % 2 == 0)
ret += use_machine({0, n - 1}) == 0;
return ret;
}
ll count_mushrooms(ll n) {
if (n < 450)
return brutforce(n);
vc<vc<ll>> p = {{0}, {}};
for (ll i = 1; sz(p[0]) < 2 and sz(p[1]) < 2; i++)
p[use_machine({0, i})].pub(i);
ll d = 0;
if (sz(p[0]) < 2)
d++;
ll x = p[d][0], y = p[d][1];
ll C = 139;
ll i = sz(p[0]) + sz(p[1]);
while (sz(p[0]) < C and sz(p[1]) < C) {
ll q = use_machine({i, x, i + 1, y});
p[d ^ (q % 2)].pub(i);
p[d ^ (q / 2)].pub(i + 1);
i += 2;
}
ll ret = sz(p[0]);
for ( ; i < n; ) {
if (sz(p[0]) >= sz(p[1])) {
ll k = sz(p[0]);
ll r = min(n - 1, i + k - 1);
vc<ll> q;
for (ll j = i; j <= r; j++) {
q.pub(j);
q.pub(p[0][j - i]);
}
x = use_machine(q);
ret += (r - i + 1) - (x + 1) / 2;
p[x % 2].pub(i);
i = r + 1;
} else {
ll k = sz(p[1]);
ll r = min(n - 1, i + k - 1);
vc<ll> q;
for (ll j = i; j <= r; j++) {
q.pub(j);
q.pub(p[1][j - i]);
}
x = use_machine(q);
ret += (x + 1) / 2;
p[1 ^ (x % 2)].pub(i);
i = r + 1;
}
}
return ret;
}
