#include <cstdio> #include <cstring> #include <algorithm> #define FILEIO #ifdef FILEIO FILE *infile=fopen("game.in","r"), *outfile=fopen("game.out","w"); #define scanf(x...) fscanf(infile,x) #define printf(x...) fprintf(outfile,x) #endif // FILEIO int n,val[1000001],a,b,tmp; struct Segment { int l, r; inline bool operator ()(Segment a,Segment b) { if(a.l==b.l) return a.r<b.r; return a.l>b.l; } }seg[500001]; inline void Val(int& a) { a=std::lower_bound(val,val+tmp,a)-val; } int L[1000003],N; int dp[500001]; int main() { scanf("%d",&n); for(int i=0;i<n;++i) { scanf("%d%d",&a,&b); seg[i]=(Segment){a,b}; val[i<<1]=a; val[i<<1|1]=b; } std::sort(val,val+(n<<1)); memset(L,0xff,sizeof(L)); N=tmp=std::unique(val,val+(n<<1))-val; for(int i=0;i<n;++i) Val(seg[i].l), Val(seg[i].r); std::sort(seg,seg+n,Segment()); for(int i=0;i<n;++i) if(~L[seg[i].l]) continue; else L[seg[i].l]=i; dp[0]=1; for(int i=1;i<n;++i) { int k,lf,l,r,mid,nxt; lf=seg[i].l; r=i-1; k=seg[i].l; while(lf<=seg[i].r) { nxt=lf; while(nxt !=N and L[++nxt]==-1) ; l=L[nxt]+1; tmp=-1; while(l<=r) { mid=(l+r)>>1; if(seg[mid].r>seg[i].r) r=mid-1; else l=(tmp=mid)+1; } if(~tmp and seg[tmp].r>k) { k=seg[tmp].r; dp[i]=std::max(dp[i],dp[tmp]); } r=L[lf]-1; lf=nxt; } dp[i]+=1; } int ans=0; for(int i=0;i<n;++i) if(dp[i]>ans) ans=dp[i]; printf("%d\n",ans); #ifdef FILEIO fclose(infile); fclose(outfile); #undef scanf #undef printf #endif // FILEIO return 0; }