#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
/*bool is_clockwise(int i, int j, int k)
{
cout << "Are the vertices numbered " << i << " " << j << " " << k << " clockwise in this order?" << endl;
string ret; cin >> ret;
return (ret[0] == 'y' || ret[0] == 'Y');
}*/
vector<int> solve(int n)
{
if(n == 3)
{
if(is_clockwise(1, 2, 3))
return {1, 2, 3};
else
return {3, 2, 1};
}
vector<int> v = solve(n-1);
int K = v.size();
//v[0], v[1], ..., v[]
int md = is_clockwise(v[0], v[1], n);
int l = 0; int r = K-1; int p = -1;//non MD element.
while(l < r)
{
if((r-l+1) <= 6)
{
while((l < r) && (is_clockwise(v[l], v[(l+1)%K], n) == md))
l++;
while((r > l) && (is_clockwise(v[r], v[(r+1)%K], n) == md))
r--;
if((l == r) && (is_clockwise(v[l], v[(l+1)%K], n) == md))
return v;
vector<int> c; c.pb(n);
if(md == 1)
{
int u = (r+1)%K; if(l < u) l+=K;
for(int t = u; t <= l; t++)
c.pb(v[t%K]);
return c;
}
else
{
int u = l; r = (r+1)%K; if(r < u) r+=K;
for(int t = u; t <= r; t++)
c.pb(v[t%K]);
}
return c;
}
int a = (2*l+r)/3; int b = (2*r+l)/3;
//[l, a, b, r]
if(is_clockwise(v[a], v[(a+1)%K], n) != md)
{
p = a;
break;
}
if(is_clockwise(v[b], v[(b+1)%K], n) != md)
{
p = b;
break;
}
l = a; r = b;
}
int L1 = 0;
int R1 = p;//first non md.
while(L1 < R1)
{
int m = (L1+R1)/2;
if(is_clockwise(v[m], v[(m+1)%K], n) != md)
R1 = m;
else
L1 = m+1;
}
int L2 = p+1;
int R2 = K;//first md.
while(L2 < R2)
{
int m = (L2+R2)/2;
if(is_clockwise(v[m], v[(m+1)%K], n) == md)
R2 = m;
else
L2 = m+1;
}
//L1, ..., R2 consists of non mds.
if(md == 0)
swap(L1, R2);
//1...L1 --> n --> R2 -->
vector<int> c; c.pb(n);
if(L1 < R2)
L1+=K;
for(int j = R2; j <= L1; j++)
c.pb(v[j%K]);
return c;
}
signed main()
{
/*int n; cin >> n;
vector<int> vv = solve(n);
cout << "Convex hull = " << endl;
for(auto tt: vv)
cout << tt << " ";
cout << endl;*/
give_answer(solve(get_n()).size());
return 0;
}
