#include "mushrooms.h"
#include <bits/stdc++.h>
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define USE use_machine
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 6e5+10;
const int MAXA = 5e4+10;
const int SQRT = 300;
const int INF = 2e9;
const int MOD = 1e9+87;
const int MOD2 = 1e9+7;
const int LOG = 30;
int n;
int count_mushrooms(int N) {
n = N;
vector<int> a = {0}, b;
int ans = 1;
vector<int> vec;
for(int i=1; i<=n-1; i++) vec.pb(i);
while(!vec.empty()){
if(b.size() < a.size()){//pake a
vector<int> m;
int tot = 0;
while(!vec.empty()){
m.pb(a[tot]); m.pb(vec.back());
tot++; vec.pop_back();
if(tot == a.size()){
// cout << m.size() << " msiz\n";
if(!vec.empty()){
m.pb(vec.back()); vec.pop_back();
int ret = USE(m);
if(ret%2 == 0){// ... .. A
ans += tot-ret/2;
ans++; a.pb(m.back());
} else { // ... A/B B
ans += tot-1-ret/2; // ret/2 = b
b.pb(m.back()); // ada b di depan
vec.pb(m[m.size()-2]);
}
} else {
int ret = USE(m);
ans += tot-1-ret/2; // ret/2 = b
if(ret%2 == 1) b.pb(m.back()); // ada b di depan
else ans++, a.pb(m.back());
}
m.clear();
tot = 0;
break;
}
}
if(!m.empty()){
// cout << m.size() << " msiz\n";
int ret = USE(m);
ans += tot-1-ret/2; // ret/2 = b
if(ret%2 == 1) b.pb(m.back()); // ada b di depan
else ans++, a.pb(m.back());
}
} else {//pake b
vector<int> m;
int tot = 0;
while(!vec.empty()){
m.pb(b[tot]); m.pb(vec.back());
tot++; vec.pop_back();
if(tot == b.size()){
if(!vec.empty()){
m.pb(vec.back()); vec.pop_back();
int ret = USE(m);
if(ret%2 == 0){// ... .. B
ans += ret/2;
b.pb(m.back());
} else { // ... A/B A
ans += ret/2; // ret/2 = b
ans++; a.pb(m.back()); // ada b di depan
vec.pb(m[m.size()-2]);
}
} else {
int ret = USE(m);
ans += ret/2; // ret/2 = b
if(ret%2 == 1) ans++, a.pb(m.back());
else b.pb(m.back()); // ada b di depan
}
m.clear();
tot = 0;
break;
}
}
if(!m.empty()){
int ret = USE(m);
ans += ret/2; // ret/2 = b
if(ret%2 == 1) ans++, a.pb(m.back());
else b.pb(m.back()); // ada b di depan
}
}
}
return ans;
}
