#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,m; struct board{ int l,r; }a[500005]; int b[1000005]; int mxn[4000005],ans,now; bool cmp(board x,board y){ if(x.r!=y.r) return x.r<y.r; else return x.l>y.l; } void modify(int k,int l,int r,int pos,int key){ if(l==r) return mxn[k]=max(mxn[k],key),void(); int mid=l+r>>1; if(pos<=mid) modify(k<<1,l,mid,pos,key); else modify(k<<1|1,mid+1,r,pos,key); mxn[k]=max(mxn[k<<1],mxn[k<<1|1]); return; } int query(int k,int l,int r,int L,int R){ if(r<L||R<l) return 0; if(L<=l&&r<=R) return mxn[k]; int mid=l+r>>1; return max(query(k<<1,l,mid,L,R),query(k<<1|1,mid+1,r,L,R)); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i+=1){ scanf("%d%d",&a[i].l,&a[i].r); b[++m]=a[i].l; b[++m]=a[i].r; } sort(b+1,b+m+1); m=unique(b+1,b+m+1)-b-1; for(int i=1;i<=n;i+=1){ a[i].l=lower_bound(b+1,b+m+1,a[i].l)-b; a[i].r=lower_bound(b+1,b+m+1,a[i].r)-b; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i+=1){ now=query(1,1,m,a[i].l,a[i].r)+1; ans=max(ans,now); modify(1,1,m,a[i].l,now); } printf("%d\n",ans); return 0; }