#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int use_machine(vector<int> x);
int count_mushrooms(int n){
vector<int> a, b;
a.pb(0);
int ans = 1, i = 1;
while(1){
if(i >= n) break;
if(SZ(a) > SZ(b)){
vector<int> v;
int j = i;
while(j < n && j < i + SZ(a)){
v.pb(a[j - i]);
v.pb(j);
j++;
}
int res = use_machine(v);
ans += SZ(v) / 2 - (res + 1) / 2;
i = j;
if(res&1){
b.pb(i - 1);
}
} else{
vector<int> v;
int j = i;
while(j < n && j < i + SZ(b)){
v.pb(b[j - i]);
v.pb(j);
j++;
}
int res = use_machine(v);
ans += (res + 1) / 2;
i = j;
if(res&1){
a.pb(i - 1);
}
}
}
return ans;
}
