#include <bits/stdc++.h>
#define forint(i, N) for (int i = 0; i < (N); i++)
using namespace std;
int use_machine(vector<int> x);
int count(char first_char, int first, int last, int& n_diff) {
if (first == last) {
if (first_char == 'A') {
return 1;
}
else {
return 0;
}
}
else {
if (n_diff < 0) {
vector<int> x;
if (first < last) {
for (int i = first; i <= last; i++) {
x.push_back(i);
}
}
else {
for (int i = first; i >= last; i--) {
x.push_back(i);
}
}
n_diff = use_machine(x);
}
int len = first < last ? last - first + 1 : first - last + 1;
if (len == 2) {
if (n_diff == 0) {
return (first_char == 'A' ? 2 : 0);
}
else {
return 1;
}
}
int mid = (first + last) / 2;
int n_diff1 = -1;
int n1 = count(first_char, first, mid, n_diff1);
char c = n_diff % 2 == 0 ? first_char : ((first_char == 'A') ? 'B' : 'A');
int n_diff2 = n_diff - n_diff1;
int n2 = count(c, last, mid, n_diff2);
char c_mid = n_diff1 % 2 == 0 ? first_char : ((first_char == 'A') ? 'B' : 'A');
if (c_mid == 'A') {
return n1 + n2 - 1;
}
else {
return n1 + n2;
}
}
}
int count_mushrooms(int n) {
int n_diff = -1;
return count('A', 0, n-1, n_diff);
}
