#include <cstdio> #include <algorithm> #include <iostream> using namespace std; struct mbn{ int l; int r; }; struct rdd{ int s; int num; }; mbn a[2000005]; rdd b[2000005]; int c[2000005]; int f[2000005]; struct trrd{ int s[5000005]; void chg(int k,int l,int r,int x,int y){ if(l==r&&l==x){ s[k]=max(s[k],y); return; } int mid=l+r>>1; if(x<=mid) chg(k<<1,l,mid,x,y); else chg(k<<1|1,mid+1,r,x,y); s[k]=max(s[k<<1],s[k<<1|1]); } int qry(int k,int l,int r,int x,int y){ if(x<=l&&r<=y) return s[k]; int mid=l+r>>1; int res=0; if(x<=mid) res=max(res,qry(k<<1,l,mid,x,y)); if(y>mid) res=max(res,qry(k<<1|1,mid+1,r,x,y)); return res; } }; trrd t; int n,m; bool cmp(mbn ax,mbn ay){ return ax.l<ay.l; } bool cp2(rdd ax,rdd ay){ return ax.s<ay.s; } int main(){ scanf("%d",&n); int i,j; for(i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r); sort(a+1,a+n+1,cmp); for(i=1;i<=n;i++){ b[i].s=a[i].r; b[i].num=i; } sort(b+1,b+n+1,cp2); for(i=1;i<=n;i++){ if(b[i].s!=b[i-1].s) m++; c[b[i].num]=m; } for(i=1;i<=n;i++){ f[i]=t.qry(1,1,m,c[i],m)+1; t.chg(1,1,m,c[i],f[i]); } printf("%d\n",t.qry(1,1,m,1,m)); return 0; }