#include<bits/stdc++.h> #define fst(a,b,c) for(int a=(b);a<=(c);a++) #define pst(a,b,c) for(int a=(b);a>=(c);a--) #define ls (rt<<1) #define rs ((rt<<1)|1) using namespace std; const int N=5e5+100,MX=1e9; int n,m,ans; int l[N],r[N],pos[N*2],ord[N]; struct Node{ int mx,tag; }t[N*8]; int read(){ char in=getchar(); int x=0; while(!isdigit(in)) in=getchar(); while(isdigit(in)) x=x*10+(in^48),in=getchar(); return x; } bool cmp(int x,int y){return (l[x]!=l[y])?(l[x]<l[y]):(r[x]<r[y]);} void up(int rt){t[rt].mx=max(t[ls].mx,t[rs].mx);} void dn(int rt){ if(!t[rt].tag) return; t[ls].mx=max(t[ls].mx,t[rt].tag); t[ls].tag=max(t[ls].tag,t[rt].tag); t[rs].mx=max(t[rs].mx,t[rt].tag); t[rs].tag=max(t[rs].tag,t[rt].tag); t[rt].tag=0; return; } int qry(int l,int r,int rt=1,int L=1,int R=m){ if(l<=L&&R<=r) return t[rt].mx; int mid=(L+R)>>1; dn(rt); if(r<=mid) return qry(l,r,ls,L,mid); else if(l>mid) return qry(l,r,rs,mid+1,R); else return max(qry(l,r,ls,L,mid),qry(l,r,rs,mid+1,R)); } void upd(int l,int r,int x,int rt=1,int L=1,int R=m){ if(l<=L&&R<=r){ t[rt].mx=max(t[rt].mx,x); t[rt].tag=max(t[rt].tag,x); return; } int mid=(L+R)>>1; dn(rt); if(l<=mid) upd(l,r,x,ls,L,mid); if(r>mid) upd(l,r,x,rs,mid+1,R); up(rt); return; } int main(){ // freopen("game.in","r",stdin); // freopen("game.out","w",stdout); int tmp; n=read(); fst(i,1,n){ pos[++m]=l[i]=read(); pos[++m]=r[i]=read(); ord[i]=i; } sort(pos+1,pos+m+1); m=unique(pos+1,pos+m+1)-pos-1; fst(i,1,n){ l[i]=lower_bound(pos+1,pos+m+1,l[i])-pos; r[i]=lower_bound(pos+1,pos+m+1,r[i])-pos; } sort(ord+1,ord+n+1,cmp); pst(i,n,1){ tmp=qry(l[ord[i]],r[ord[i]])+1; upd(r[ord[i]],m,tmp); ans=max(ans,tmp); } printf("%d\n",ans); return 0; } /* 5 1 10 2 9 3 8 4 7 5 6 */