#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;
for (int i = first; i <= last; i++) {
x.push_back(i);
}
n_diff = use_machine(x);
}
int len = last - first + 1;
if (n_diff == 0) {
return (first_char == 'A' ? len : 0);
}
else if (n_diff == len-1) {
if (len % 2 == 0) {
return len / 2;
}
else {
if (first_char == 'A') {
return len / 2 + 1;
}
else {
return len / 2;
}
}
}
int mid = (first + last) / 2;
int n_diff1 = -1;
int n1 = count(first_char, first, mid, n_diff1);
char c = n_diff1 % 2 == 0 ? first_char : ((first_char == 'A') ? 'B' : 'A');
int n_diff2 = n_diff - n_diff1;
int n2 = count(c, mid, last, n_diff2);
if (c == '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);
}
