#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int HSQ = 70;
int THSQ = 2*HSQ+1;
int count_mushrooms(int n) {
if(n<=140) {
int ans = 1;
for(int i=1;i<n;i++) ans += !use_machine({0,i});
return ans;
}
bool st[THSQ]; st[0]=1;
for(int i=1;i<THSQ;i++) st[i]=!use_machine({0,i});
vector<int> A, B;
for(int i=0;i<THSQ;i++) {
if(st[i]) A.push_back(i);
else B.push_back(i);
}
int ans = A.size();
if(A.size()>B.size()) {
vector<int> v={A[0]};
for(int j=THSQ;j<n;j++) {
v.push_back(j);
v.push_back(A[((j-1)%HSQ)+1]);
if(j==n-1||(!(j%HSQ))) {ans += (v.size()-1-use_machine(v))/2; v={A[0]};}
}
} else {
vector<int> v={B[0]};
for(int j=THSQ;j<n;j++) {
v.push_back(j);
v.push_back(B[((j-1)%HSQ)+1]);
if(j==n-1||!(j%HSQ)) {ans += use_machine(v)/2; v={B[0]};}
}
}
return ans;
}
