///
/// Standing here
/// I realize
/// You are just like me
/// Trying to make history
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
#ifndef LOCAL
#include "mushrooms.h"
#else
int count_mushrooms(int n);
const int a[] = {0, 1, 0, 0};
const int n = sizeof(a)/sizeof(a[0]);
int use_machine(vector<int> v)
{
int ans = 0;
Loop (i,0,v.size()-1)
ans += a[v[i]] != a[v[i+1]];
return ans;
}
int main()
{
int ans = 0;
Loop (i,0,n) ans += !a[i];
cout << ans << '\n';
cout << count_mushrooms(n) << '\n';
}
#endif
int count_mushrooms(int n) {
vector<int> known[2];
known[0].push_back(0);
int p = 1;
int ans = 1;
while (p < n) {
int c = known[0].size() < known[1].size();
int x = known[c].size();
if (x < 80 && x > 1)
x = 2;
x = min(x, n - p);
vector<int> vec;
Loop (i,0,x) {
vec.push_back(known[c][i]);
vec.push_back(p+i);
}
int y = use_machine(vec);
known[(y&1)^c].push_back(p+x-1);
if (x == 2)
known[(y>>1)^c].push_back(p);
ans += c? (y+1)/2: x - (y+1)/2;
p += x;
}
return ans;
}
