#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;
#define ST first
#define ND second
#define PB push_back
const int B = 250;
vi a, b;
int use_machine(vi x);
int count_mushrooms(int n) {
srand(time(NULL));
if(n == 1) return 1;
vi v(n-1);
a = {};
b = {};
for(int i = 1; i < n; ++i) v[i - 1] = i;
random_shuffle(v.begin(), v.end());
a.PB(0);
for(int i = 0; i < min(n - 1, B); ++i) {
int w = use_machine({0, v[i]});
if(w == 1) b.PB(v[i]);
else a.PB(v[i]);
}
int ans = (int)a.size();
bool inv = 0;
if((int)a.size() < (int)b.size()) {
swap(a, b);
inv = 1;
}
for(int i = B; i < n - 1; i++) {
vi s = {};
int nxt = 0, all = 0;
int last = 0;
for(int j = i; j < min(n - 1, i + (int)a.size()); ++j) {
s.PB(a[nxt++]);
s.PB(v[j]);
all++;
last = j;
}
int w = use_machine(s);
if(!inv) {
int cntB = w / 2 + (w % 2);
ans += all - cntB;
if(w%2 == 0) {
a.PB(v[last]);
}
} else {
ans += w/2 + (w%2);
if(w % 2 == 0) {
a.PB(v[last]);
}
}
i = last;
}
return ans;
}
