// ~Be name khoda~ //
#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
#define endll '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const int sq = 200;
const ll inf = 2e18;
int nxt[maxn5], pre[maxn5];
int per[maxn5], st, sqnxt[maxn5];
inline bool clk(int a, int b, int c){
return is_clockwise(per[a], per[b], per[c]);
}
inline int get(int d){
int v = st;
while(d >= sq){
d -= sq;
v = sqnxt[v];
}
while(d--)
v = nxt[v];
return v;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n = get_n();
nxt[1] = 2; nxt[2] = 3; nxt[3] = 1;
pre[1] = 3; pre[2] = 1; pre[3] = 2;
int need = sq;
sqnxt[1] = 1; sqnxt[2] = 2; sqnxt[3] = 3;
while(need--){
sqnxt[1] = nxt[sqnxt[1]];
sqnxt[2] = nxt[sqnxt[2]];
sqnxt[3] = nxt[sqnxt[3]];
}
if(n == 3){
give_answer(3);
return 0;
}
st = 1;
int sz = 3;
for(int i = 1; i <= n; i++)
per[i] = i;
shuffle(per + 1, per + n + 1, rng);
for(int i = 4; i <= n; i++){
int out = -1;
bool hullorder = clk(st, nxt[st], nxt[nxt[st]]);
bool ans = clk(st, nxt[st], i);
ans ^= hullorder;
if(ans){
out = st;
}
else{
int lo = 0, hi = sz - 2;
while(hi - lo > 1){
int mid = (lo + hi) >> 1;
if(hullorder ^ clk(st, get(mid + 1), i))
hi = mid;
else
lo = mid;
}
//cout << "here " << st << ' ' << sz << ' ' << lo << ' ' << hi << endl;
if(hi == sz - 2 && clk(st, pre[st], nxt[st]) != clk(st, pre[st], i)){
lo = hi;
//cout << "oh spc case " << endl;
if(clk(pre[st], st, nxt[st]) != clk(pre[st], st, i))
out = pre[st];
}
else{
int lolo = get(lo + 1);
if(clk(lolo, nxt[lolo], nxt[nxt[lolo]]) != clk(lolo, nxt[lolo], i))
out = lolo;
}
}
//cout << "chaka chaka " << i << ' ' << out << endl;
if(out == -1)
continue;
for(out = nxt[out]; ; out = nxt[out])
if(clk(out, nxt[out], nxt[nxt[out]]) == clk(out, nxt[out], i))
break;
int r = out;
for(out = pre[out]; ; out = pre[out]){
if(clk(out, pre[out], pre[pre[out]]) == clk(out, pre[out], i))
break;
sz--;
}
sz++;
int l = out;
//cout << "hola " << r << endl;
//cout << "wow it's " << l << endl;
nxt[l] = i;
pre[r] = i;
nxt[i] = r;
pre[i] = l;
st = i;
int need = sq;
int have = i;
while(need--)
have = nxt[have];
sqnxt[i] = have;
need = sq + 4;
have = i;
while(need--){
have = pre[have];
sqnxt[have] = pre[sqnxt[nxt[have]]];
}
/*
cout << "let's check " << i << endl;
int j = st;
cout << j << ' ';
j = nxt[j];
while(j != st){
cout << j << ' ';
j = nxt[j];
}
cout << endl;
cout << "and finaly " << sz << endl;
//*/
}
int num = 1;
for(int i = nxt[st]; i != st; i = nxt[i]) num++;
give_answer(num);
}
