#include<bits/stdc++.h> #define I using #define love namespace #define Elaina std const int N=500010; I love Elaina; int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); } return x*f; } int n,m,pos[N<<1],f[N],ans; struct qry{ int l,r; bool operator<(const qry &rhs)const{ return l!=rhs.l?l<rhs.l:r>rhs.r; } }q[N]; namespace AyaseEli{ #define ls(k) (k<<1) #define rs(k) (k<<1|1) struct node{ int maxn,l,r; }tree[N<<3]; void pushup(node *tree,int k){ tree[k].maxn=max(tree[ls(k)].maxn,tree[rs(k)].maxn); } void build(node *tree,int k,int l,int r){ tree[k].l=l,tree[k].r=r; if(l==r)return; int mid=(l+r)/2; build(tree,ls(k),l,mid),build(tree,rs(k),mid+1,r); pushup(tree,k); } void modify(node *tree,int k,int q,int v){ if(tree[k].l==tree[k].r){ tree[k].maxn=max(tree[k].maxn,v); return; } int mid=(tree[k].l+tree[k].r)/2; if(q<=mid)modify(tree,ls(k),q,v); else modify(tree,rs(k),q,v); pushup(tree,k); } int query(node *tree,int k,int ql,int qr){ int res=0; if(ql<=tree[k].l&&tree[k].r<=qr)return tree[k].maxn; int mid=(tree[k].l+tree[k].r)/2; if(ql<=mid)res=max(res,query(tree,ls(k),ql,qr)); if(mid<qr)res=max(res,query(tree,rs(k),ql,qr)); return res; } } I love AyaseEli; int main(){ n=read(); for(int i=1;i<=n;i++)q[i]=(qry){read(),read()},pos[2*i-1]=q[i].l,pos[2*i]=q[i].r; sort(pos+1,pos+2*n+1); m=unique(pos+1,pos+2*n+1)-pos-1; build(tree,1,1,m); for(int i=1;i<=n;i++)q[i].l=lower_bound(pos+1,pos+m+1,q[i].l)-pos,q[i].r=lower_bound(pos+1,pos+m+1,q[i].r)-pos; sort(q+1,q+n+1); for(int i=1;i<=n;i++){ f[i]=query(tree,1,q[i].r,m)+1; modify(tree,1,q[i].r,f[i]); ans=max(ans,f[i]); } printf("%d",ans); return 0; }