#include "mushrooms.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
int K = 80;
vector<vector<bool> > S[8]; int Q[8],F[8];
void calc(){
S[0] = {{true}};
Q[0] = 1;
F[0] = 1;
forf(k,1,7){
F[k] = 2*F[k-1] + Q[k-1]-1;
Q[k] = 2*Q[k-1];
S[k].resize(Q[k],vector<bool>(F[k],false));
forf(j,F[k-1],2*F[k-1]-1) S[k][0][j] = true;
forf(i,0,Q[k-1]-2){
forf(j,0,F[k-1]-1) S[k][2*i+1][j] = S[k-1][i][j], S[k][2*i+1][F[k-1]+j] = S[k-1][i][j];
forf(j,0,F[k-1]-1) S[k][2*i+2][j] = S[k-1][i][j], S[k][2*i+2][F[k-1]+j] = !S[k-1][i][j];
S[k][2*i+2][2*F[k-1]+i] = true;
}
forf(j,0,F[k]-1) S[k][Q[k]-1][j] = true;
}
}
vector<int> eval(int k, vector<int> sum){
assert(sz(sum) == Q[k]);
if(k==0) return sum;
vector<int> l(Q[k-1],0),r(Q[k-1],0),res(F[k],0);
int ra = sum[0];
int la = sum.back()-sum[0];
forf(i,0,Q[k-1]-2){
sum[2*i+2] -= ra;
if((sum[2*i+1]+1000)%2 != (sum[2*i+2]+1000)%2) res[2*F[k-1]+i] = 1, sum[2*i+2]--, la--;
l[i] = (sum[2*i+1]+sum[2*i+2])/2;
r[i] = (sum[2*i+1]-sum[2*i+2])/2;
}
l[Q[k-1]-1] = la, r[Q[k-1]-1] = ra;
vector<int> resl = eval(k-1,l), resr = eval(k-1,r);
forf(i,0,F[k-1]-1) res[i] = resl[i], res[F[k-1]+i] = resr[i];
return res;
}
vector<int> A,B;
deque<int> C;
int ans = 0;
void go1(){
vector<int> q;
int f = 0;
if(sz(A) < sz(B)) f=1, swap(A,B);
int fst = -1, sec = -1;
q.pb(C.front()), fst=C.front(), C.pop_front(), q.pb(A[0]);
if(sz(A) >= 2 && sz(C)) q.pb(C.front()), sec = C.front(), C.pop_front(), q.pb(A[1]);
int res = use_machine(q);
if(res & 1) B.pb(fst);
else A.pb(fst);
if(sec!=-1) {
if (res & 2) B.pb(sec);
else A.pb(sec);
}
if(f) swap(A,B);
}
void go10(){
int f = 0;
if(sz(A) < sz(B)) f=1, swap(A,B);
int k = 0;
while(k+1<=7 && F[k+1]+1 <= sz(A) && sz(C) > F[k+1]+Q[k+1]) k++;
vector<int> sum;
forf(i,0,Q[k]-1){
vector<int> q;
forf(j,0,F[k]-1){
q.pb(A[j]);
if(S[k][i][j]) q.pb(C[j]);
}
q.pb(A[F[k]]);
q.pb(C.back());
int res = use_machine(q);
if(res%2) B.pb(C.back()), C.pop_back();
else A.pb(C.back()), C.pop_back();
sum.pb(res/2);
}
auto e = eval(k,sum);
forf(i,0,F[k]-1){
if(e[i]) B.pb(C[i]);
else A.pb(C[i]);
}
forf(i,0,F[k]-1) C.pop_front();
if(f) swap(A,B);
}
void go2(){
vector<int> q;
int f = 0;
if(sz(A) < sz(B)) f=1, swap(A,B);
int fst = C.front();
int cnt = -1;
for(auto i : A){
if(sz(C)) q.pb(C.front()), C.pop_front(), cnt++;
q.pb(i);
}
int res = use_machine(q);
if(f == 0){
if(res % 2) B.pb(fst);
else A.pb(fst);
ans += cnt - res/2;
}
else{
if(res % 2) B.pb(fst);
else A.pb(fst);
ans += res/2;
}
if(f) swap(A,B);
}
int count_mushrooms(int n) {
calc();
A.pb(0);
forf(i,1,n-1) C.pb(i);
if(n <= 400){
while(sz(C)) go1();
}
else{
while(sz(C) && (sz(A) < 2 && sz(B) < 2)) go1();
while(sz(C) && (sz(A) < K && sz(B) < K)) go10();
while(sz(C)) go2();
}
return sz(A)+ans;
}
