#include "mushrooms.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 1e9;
const int N = 2e4 + 5;
int use_machine(std::vector<int> x);
mt19937_64 rng(696969);
int s , tim;
int rand(int n){
ll x = rng();
return abs(x) % (n + 1);
}
vector<int> t(N * 4);
void build(int v , int l , int r){
if(r - l == 1) t[v] = 1;
else {
int m = (l + r) / 2;
build(v * 2 , l , m);
build(v * 2 + 1 , m , r);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
void update(int v , int l , int r , int j){
if(r - l == 1) t[v] = 0;
else{
int m = (l + r) / 2;
if(j < m) update(v * 2 , l , m , j);
else update(v * 2 + 1 , m , r , j);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
int gett_ps(int v , int l , int r , int x){
if(r - l == 1) return l;
int m = (l + r) / 2;
if(t[v * 2] >= x){
return gett_ps(v * 2 , l , m , x);
}
else{
return gett_ps(v * 2 + 1 , m , r , x - t[v * 2]);
}
return 0;
}
int get(int x){ return gett_ps(1 , 0 , s , x); }
void upd(int p){
update(1 , 0 , s , p);
}
int count_mushrooms(int n) {
s = n;
build(1 , 0 , n);
upd(0);
int sz = n - 1;
int ans = 1;
vector<int> psa , psb;
psa.push_back(0);
int j = 1;
while(j < n){
vector<int> ps;
bool pa = true;
int msz = 0;
if(psa.size() >= psb.size()){
msz = psa.size();
for(auto to : psa) ps.push_back(to);
}
else{
pa = false;
msz = psb.size();
for(auto to : psb) ps.push_back(to);
}
int lps = j , c = 0;
vector<int> qu;
for(int i = j;i < min(n , j + msz); ++ i){
// random
int p0 = rand((-- sz));
int rps = get(p0 + 1);
lps = rps;
upd(rps);
qu.push_back(ps[i - j]);
qu.push_back(rps);
c ++;
}
j = min(n , j + msz);
//cout << c << ' ' << pa << '\n';
int k = use_machine(qu);
if(! pa){
ans += (k + 1) / 2;
if(k % 2 == 0) psb.push_back(lps);
else psa.push_back(lps);
}
else{
ans += (c - (k + 1) / 2);
if(k % 2 == 1) psb.push_back(lps);
else psa.push_back(lps);
}
}
return ans;
}
