#include "trilib.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ld>pairld;
typedef pair<string,ll>pairsl;
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
#define MOD 1000000007
#define INF 10000000000007
#define eps 0.00000000001
#define A 50
#define PI 3.14159265359
ll n,d[40007],mn,mx;
deque<pairll>v,a;
map<pair3l,ll>m;
ll cl(ll x,ll y,ll z){
if(m[{x,{y,z}}]==0){
m[{x,{y,z}}]=ll(is_clockwise(x,y,z))+1;
}
return m[{x,{y,z}}]-1;
}
pair3l S(ll l,ll r,ll z,ll l1,ll r1){
//cout<<"? "<<l<<" "<<r<<" "<<l1<<" "<<r1<<endl;
if(cl(v[l].fr,z,v[r].sc)==0){
if(l1==1){
if(cl(v[l].fr,z,v[l].sc)==0){
if(r1==1){
if(cl(v[r].fr,z,v[r].sc)==0)return {0,{0,0}};
}else if(r1==0)return {0,{0,0}};
}
}else if(r1==1){
if(cl(v[r].fr,z,v[r].sc)==0)return {0,{0,0}};
}else return {0,{0,0}};
}
//cout<<l<<" "<<r<<endl;
if(l==r){
//cout<<"-"<<l<<endl;
d[l]=z;
mn=min(l,mn);
mx=max(mx,l);
return {1,{1,1}};
}
ll m1=(l+r)/2;
pair3l tl=S(l,m1,z,l1,0);
if(tl.fr==1){
return {1,{tl.sc.fr,S(m1+1,r,z,tl.sc.sc,r1).sc.sc}};
}else{
tl=S(m1+1,r,z,0,r1);
if(tl.sc.fr==1)return {1,{S(l,m1,z,l1,tl.sc.fr).sc.fr,tl.sc.sc}};
else return {1,{0,tl.sc.sc}};
}
}
int main(){
n=get_n();
ll x=is_clockwise(1,3,2);
if(x==1){
v.pb({1,3});
v.pb({3,2});
v.pb({2,1});
}else{
v.pb({1,2});
v.pb({2,3});
v.pb({3,1});
}
for(int i=4;i<=n;i++){
//m.clear();
mn=v.size();
mx=-1;
pair3l tl=S(0,(v.size()-1)/2,i,0,0);
if(tl.fr==1){
S((v.size()-1)/2+1,v.size()-1,i,tl.sc.sc,tl.sc.fr);
}else{
tl=S((v.size()-1)/2+1,v.size()-1,i,0,0);
if(tl.sc.sc==1 || tl.sc.fr==1)S(0,(v.size()-1)/2,i,tl.sc.sc,tl.sc.fr);
}
if(mn!=v.size()){
if(mn==0){
if(mx==v.size()-1){
while(d[v.size()-1]==i)v.pop_back();
v.pb({v.back().sc,i});
ll y=0;
while(d[y]==i){
y++;
v.pop_front();
}
v.push_front({i,v.front().fr});
}else{
x=v.front().fr;
ll y=0;
while(d[y]==i){
y++;
v.pop_front();
}
v.push_front({i,v.front().fr});
v.push_front({x,i});
}
}else{
ll y=0;
while(d[y]!=i){
y++;
v.pb(v.front());
v.pop_front();
}
x=v.front().fr;
while(d[y]==i){
y++;
v.pop_front();
}
v.push_front({i,v.front().fr});
v.push_front({x,i});
}
}
//cout<<"! "<<endl;
// for(auto it:v)cout<<it.fr<<" "<<it.sc<<endl;
//cout<<endl;
}
give_answer(v.size());
return 0;
}
/*
8
1 1
1 18
4 16
6 14
7 11
6 8
4 4
15 10
*/
