// In the name of Allah
#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 20000 + 4;
const int M = 141;
vector<int> ls[2], lsx;
int col[maxn];
int count_mushrooms(int n) {
int j = 0, T = 0;
while (j < n) {
if (j + 1 >= n || max(len(ls[0]), len(ls[1])) <= 1) {
if (j == 0) col[j] = 0;
else if (use_machine({0, j}) == 1) col[j] = 1;
else col[j] = 0;
T = 1;
}
else {
int R = 0;
if (len(ls[1]) >= len(ls[0])) R = 1;
int x = use_machine({ls[R][0], j, ls[R][1], j + 1});
if (x == 0) col[j] = col[j + 1] = R;
else if (x == 1) {
col[j] = R; col[j + 1] = 1 - R;
}
else if (x == 2) {
col[j] = 1 - R; col[j + 1] = R;
}
else col[j] = col[j + 1] = 1 - R;
T = 2;
}
while (T--) {
ls[col[j]].pb(j); j++;
}
if (max(len(ls[0]), len(ls[1])) >= M) break;
}
int res = len(ls[0]);
if (n <= j) return res;
int mx = max(len(ls[0]), len(ls[1]));
for (int i = j; i < n; i += mx) {
lsx.clear();
for (int j = i; j < min(n, i + mx); j++) {
lsx.pb(j);
if (len(ls[0]) >= len(ls[1])) lsx.pb(ls[0][j - i]);
else lsx.pb(ls[1][j - i]);
}
int t1 = (use_machine(lsx) + 1) / 2, t2 = (min(n, i + mx) - i) - t1;
if (len(ls[0]) >= len(ls[1])) res += t2;
else res += t1;
}
return res;
}
