#include "mushrooms.h"
#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int randint(int l,int r){
return uniform_int_distribution < int > (l,r) (rng);
}
///shuffle(a.begin(), a.end(), rng)
//#define int long long
const int MAX=20000+4,inf=1e9,M2=5e5+3,K=100;
void maxx(int &a,int b){if(b>a) a=b;}
void minn(int &a,int b){if(b<a) a=b;}
template <class X, class Y>
bool cmin(X &a, const Y &b) {
return a > b ? a = b, 1 : 0;
}
bool cmax(int &a,int b){
if(b>a){a=b;return 1;} else return 0;
}
typedef pair < int, int > ii;
int a[MAX];
///g++ mushrooms.cpp stub.cpp -std=c++14 -O2
int count_mushrooms(int n) {
vector<int> vec,v0,v1;
for(int i=0;i<n;i++) a[i]=i;
shuffle(a+1,a+n,rng);
v0.pb(0);
int cn=0,ans=1;
if(n>2000){
vec.pb(0);
vec.pb(a[++cn]);
int x=use_machine(vec);
if(x&1) v1.pb(a[cn]);
else {v0.pb(a[cn]);ans++;}
if(v0.size()==1){
vec.clear();
vec.pb(0);
vec.pb(a[++cn]);
int x=use_machine(vec);
if(x&1) v1.pb(a[cn]);
else {v0.pb(a[cn]);ans++;}
}
vec.clear();
if(v0.size()==2){
for(int i=0;i<K;i++){
vec.clear();
vec.pb(v0[0]);
vec.pb(a[++cn]);
vec.pb(v0.back());
vec.pb(a[++cn]);
int x=use_machine(vec);
if(x&1)v1.pb(a[cn]);
else {v0.pb(a[cn]);ans++;}
if(x&2)v1.pb(a[cn-1]);
else {v0.pb(a[cn-1]);ans++;}
}
}
else{
for(int i=0;i<K;i++){
vec.clear();
vec.pb(v1[0]);
vec.pb(a[++cn]);
vec.pb(v1.back());
vec.pb(a[++cn]);
int x=use_machine(vec);
if(x&1){v0.pb(a[cn]);ans++;}
else v1.pb(a[cn]);
if(x&2){v0.pb(a[cn-1]);ans++;}
else v1.pb(a[cn-1]);
}
}
}
while(cn!=n-1){
vec.clear();
int dem=0;
if(v0.size()>v1.size()){
for(int u:v0)if(cn<n-1){
vec.pb(u);
vec.pb(a[++cn]);dem++;
}
int x=use_machine(vec);
ans+=(dem-1-x/2);
if(x&1)v1.pb(a[cn]);
else {
v0.pb(a[cn]);
ans++;
}
}
else{
/*for(int u:v0){
vec.pb(u);
if(cn<n-1 && u!=v0.back())vec.pb(++cn);
}*/
for(int u:v1)if(cn<n-1){
vec.pb(u);
vec.pb(a[++cn]);dem++;
}
int x=use_machine(vec);
ans+=x/2;
if(x&1){
v0.pb(a[cn]);ans++;
}
else v1.pb(a[cn]);
}
}
return ans;
}
