#include "mushrooms.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int THR = 79 * 2 + 3;
int count_mushrooms(int n) {
if(n <= 400){
int cnt = 1;
for(int i=1; i+1<n; i+=2){
cnt += 2 - use_machine({i + 1, 0, i});
}
if(n % 2 == 0) cnt += 1 - use_machine({0, n - 1});
return cnt;
}
vector<int> A, B;
A.push_back(0);
if(!use_machine({0, 1})) A.push_back(1);
else B.push_back(1);
if(!use_machine({0, 2})) A.push_back(2);
else B.push_back(2);
bool flag = 0;
if(sz(A) == 1){
flag = 1;
swap(A, B);
}
for(int i = 3; i < THR; i += 2){
int kek = use_machine({A[0], i, A[1], i + 1});
if(kek & 2) B.push_back(i);
else A.push_back(i);
if(kek & 1) B.push_back(i + 1);
else A.push_back(i + 1);
}
if(flag) swap(A, B);
int pos = THR;
int surplus = 0;
while(pos < n){
vector<int> kek;
for(int i = 0; i < max(sz(A), sz(B)); i++){
kek.push_back(pos);
pos++;
if(pos == n) break;
}
if(sz(A) >= sz(B)){
vector<int> ans;
for(int i = 0; i < sz(kek); i++){
ans.push_back(kek[i]);
ans.push_back(A[i]);
}
int q = use_machine(ans);
surplus += sz(kek) - 1 - (q / 2);
if(q & 1) B.push_back(kek[0]);
else A.push_back(kek[0]);
}
else{
vector<int> ans;
for(int i = 0; i < sz(kek); i++){
ans.push_back(kek[i]);
ans.push_back(B[i]);
}
int q = use_machine(ans);
surplus += (q / 2);
if(q & 1) A.push_back(kek[0]);
else B.push_back(kek[0]);
}
}
return sz(A) + surplus;;
}
