#include<bits/stdc++.h>
#include"trilib.h" 
#define is is_clockwise
using namespace std;
int id[40005];
vector<int> p;
int n,m;
inline int pre(int x){return !x?m-1:x-1;}
inline int suf(int x){return x+1==m?0:x+1;}
void mfy(int x,int k){
    int pr=x,su=x;
    while (is(p[pre(pr)],p[pr],k)==1) pr=pre(pr);
    while (is(p[suf(su)],p[suf(suf(su))],k)==1) su=suf(su);
    if (pr==su){
        p.insert(p.begin()+pr+1,k);
    }
    else{
        pr=suf(pr);
        if (pr<=su){
            p.erase(p.begin()+pr,p.begin()+su+1);
            p.insert(p.begin()+pr,k);
        }
        else{
            p.erase(p.begin()+pr,p.end());
            p.erase(p.begin(),p.begin()+su+1);
            p.emplace_back(k);
        }
    }
}
void ins(int x){
    m=p.size();
    if (is(x,p[0],p[1])==1)
        return mfy(0,x),void();
    if (is(x,p[m-1],p[0])==1)
        return mfy(m-1,x),void();
    int l=1,r=m-2;
    while (l<r){
        int mid=(l+r)>>1;
        if (is(p[0],p[mid+1],x)==1) r=mid;
        else l=mid+1;
    }
    if (is(p[l],p[l+1],x)==1)
        mfy(l,x);
}
int main(){
    n=get_n();
    for (int i=1;i<=n;++i) id[i]=i;
    // shuffle(id+1,id+1+n,mt19937(20060430));

    shuffle(id+1,id+1+n,mt19937(time(0)));
    if (!is(id[1],id[2],id[3])) p={id[1],id[2],id[3]};
    else p={id[1],id[3],id[2]};
    for (int i=4;i<=n;++i) ins(id[i]);
    give_answer(p.size());
    return 0;
}