using Lib; using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Runtime.CompilerServices; using System.Text; using static Lib.OutputLib; public class Solver { const bool MultiTestCase = false; void Solve() { int n = ri; ReadArray(out (int a, int b)[] ab, n, () => (ri, ri)); Array.Sort(ab, (p1, p2) => p1.b - p2.b); var set = new RedBlackTree(x => x); foreach (var (a, b) in ab) { long idx = set.LowerBoundKey(a + 1) - 1; if (idx != -1) set.RemoveAt(idx); set.Add(b); } Write(set.Count() - 1); } #pragma warning disable CS0162 public Solver() { if (!MultiTestCase) Solve(); else for (int t = ri; t > 0; t--) Solve(); } #pragma warning restore CS0162 const int IINF = 1 << 30; const long INF = 1L << 60; int ri { [MethodImpl(256)] get => (int)sc.Integer(); } long rl { [MethodImpl(256)] get => sc.Integer(); } uint rui { [MethodImpl(256)] get => (uint)sc.UInteger(); } ulong rul { [MethodImpl(256)] get => sc.UInteger(); } double rd { [MethodImpl(256)] get => sc.Double(); } string rs { [MethodImpl(256)] get => sc.Scan(); } string rline { [MethodImpl(256)] get => sc.Line(); } public StreamScanner sc = new StreamScanner(Console.OpenStandardInput()); void ReadArray(out int[] a, int n) { a = new int[n]; for (int i = 0; i < a.Length; i++) a[i] = ri; } void ReadArray(out long[] a, int n) { a = new long[n]; for (int i = 0; i < a.Length; i++) a[i] = rl; } void ReadArray(out T[] a, int n, Func read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(); } } static class Program { static public void Main(string[] args) { SourceExpander.Expander.Expand(); Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); new Solver(); Console.Out.Flush(); } } #region Expanded by https://github.com/kzrnm/SourceExpander public class RedBlackTree:IEnumerable{private readonly Func_keySelector;private readonly IComparer_keyComparer;class Node{public Node?Parent{get;set;}public Node?LChild{get;set;}public Node?RChild{get;set;}public int Color{get;set;}public long CountSum{get;set;}public long Count{get;set;}public TKey Key{get;}public TValue Value{get;}public void ReplaceChild(Node?x,Node?y=null){if(LChild==x)LChild=y;if(RChild==x)RChild=y;}public Node(TKey _key,TValue _val,long _count,Node?_par=null,int _color=0){Key=_key;Value=_val;Count=_count;CountSum=Count;Color=_color;Parent=_par;LChild=null;RChild=null;}public override string ToString()=>$"[{Parent}]->{Value}*{Count}[{Color}]->[{LChild},{RChild}]:{CountSum}";}public IEnumeratorGetEnumerator()=>ToList().GetEnumerator();IEnumerator IEnumerable.GetEnumerator()=>GetEnumerator();Node?Root;public long CountAll{get;private set;}public RedBlackTree(FunckeySelector):this(keySelector,Comparer.Default){}public RedBlackTree(FunckeySelector,IComparerkeyComparer){_keyComparer=keyComparer;_keySelector=keySelector;Root=null;CountAll=0;}[MethodImpl(256)]public override string ToString()=>string.Join(",",ToList());Listlist;[MethodImpl(256)]public ListToList(){list=new List();ToList(Root);return list;}[MethodImpl(256)]private void ToList(Node?x){if(x==null)return;ToList(x.LChild);for(int i=0;iDebug(Root,"","");[MethodImpl(256)]private string Debug(Node?x,string indent,string prefix){if(x==null)return "";if(indent.Length>40)return "...";var newindent=indent+" ";var ret="";var t=Debug(x.LChild,newindent,"/");if(t!="")ret+=t;ret+=$"{indent}{prefix}{(x.Color==0?"B":"R")}:{x.Value}*{x.Count}<{x.CountSum}";t=Debug(x.RChild,newindent,"\\");if(t!="")ret+=t;return ret;}[MethodImpl(256)]public bool Contains(TValue v)=>Contains(Root,_keySelector(v));[MethodImpl(256)]private bool Contains(Node?x,TKey k){while(true){if(x==null)return false;if(_keyComparer.Compare(k,x.Key)==0)return true;x=_keyComparer.Compare(k,x.Key)<0?x.LChild:x.RChild;}}[MethodImpl(256)]public long Count()=>Root==null?0:Root.CountSum;[MethodImpl(256)]public long Count(TValue v)=>Count(Root,_keySelector(v));[MethodImpl(256)]private long Count(Node?x,TKey k){while(true){if(x==null)return 0;if(_keyComparer.Compare(k,x.Key)==0)return x.Count;x=_keyComparer.Compare(k,x.Key)<0?x.LChild:x.RChild;}}[MethodImpl(256)]public long UpperBound(TValue v)=>UpperBoundKey(_keySelector(v));[MethodImpl(256)]public long UpperBoundKey(TKey k){if(Root==null)return 0;Node?x=Root;long ret=0;while(x!=null){if(_keyComparer.Compare(k,x.Key)<0){x=x.LChild;}else{ret+=x.Count+(x.LChild!=null?x.LChild.CountSum:0);x=x.RChild;}}return ret;}[MethodImpl(256)]public long LowerBound(TValue v)=>LowerBoundKey(_keySelector(v));[MethodImpl(256)]public long LowerBoundKey(TKey k){if(Root==null)return 0;Node?x=Root;long ret=0;while(x!=null){if(_keyComparer.Compare(k,x.Key)<=0){x=x.LChild;}else{ret+=x.Count+(x.LChild!=null?x.LChild.CountSum:0);x=x.RChild;}}return ret;}public TValue this[long i]{[MethodImpl(256)]get=>GetByIndex(i);}[MethodImpl(256)]public TValue GetByIndex(long i){if((ulong)i>=(ulong)CountAll)throw new IndexOutOfRangeException();Node?x=Root;long cnt=0;while(true){if(x==null)throw new IndexOutOfRangeException();long lcnt=x.LChild==null?0:x.LChild.CountSum;if(iMaxNode(Root).Value;[MethodImpl(256)]private Node MaxNode(Node?x){if(x==null)throw new IndexOutOfRangeException();while(x.RChild!=null)x=x.RChild;return x;}[MethodImpl(256)]public TValue Min()=>MinNode(Root).Value;[MethodImpl(256)]private Node MinNode(Node?x){if(x==null)throw new IndexOutOfRangeException();while(x.LChild!=null)x=x.LChild;return x;}[MethodImpl(256)]public void Add(TValue v,long cnt=1){if(Root==null)Root=new Node(_keySelector(v),v,cnt);else Add(Root,v,cnt);CountAll+=cnt;}[MethodImpl(256)]private void Add(Node x,TValue v,long cnt){TKey k=_keySelector(v);while(true){if(_keyComparer.Compare(k,x.Key)==0){x.Count+=cnt;Node?t=x;while(t!=null){t.CountSum+=cnt;t=t.Parent;}return;}else{int dir=_keyComparer.Compare(k,x.Key)<0?0:1;Node?c=dir==0?x.LChild:x.RChild;if(c==null){c=new Node(k,v,cnt,x,1);if(dir==0)x.LChild=c;else x.RChild=c;Node?t=x;while(t!=null){t.CountSum+=cnt;t=t.Parent;}AddFix(c);return;}x=c;}}}[MethodImpl(256)]private void AddFix(Node x){while(true){var p=x.Parent;if(p==null){x.Color=0;return;}if(p.Color==0)return;var pp=p.Parent;if(pp==null){p.Color=0;return;}int dir=pp.LChild==p?0:1;var ppc=dir==0?pp.RChild:pp.LChild;if(ppc!=null&&ppc.Color==1){p.Color=0;ppc.Color=0;pp.Color=1;x=pp;continue;}else if((dir==0)^(x==p.RChild)){pp.Color=1;p.Color=0;Rotate(pp,dir^1);return;}else{pp.Color=1;x.Color=0;Rotate(p,dir);Rotate(pp,dir^1);return;}}}[MethodImpl(256)]public void RemoveAt(long x)=>Remove(Root,GetByIndex(x),1);[MethodImpl(256)]public void Remove(TValue v,long cnt=1)=>Remove(Root,v,cnt);[MethodImpl(256)]private void Remove(Node?x,TValue v,long cnt){TKey k=_keySelector(v);while(true){if(x==null)return;if(_keyComparer.Compare(k,x.Key)==0){if(x.Count>cnt){CountAll-=cnt;x.Count-=cnt;var t=x;while(t!=null){t.CountSum-=cnt;t=t.Parent;}}else{cnt=x.Count;CountAll-=cnt;Node?p=x.Parent,l=x.LChild,r=x.RChild;var t=p;while(t!=null){t.CountSum-=cnt;t=t.Parent;}if(l==null){if(p==null)Root=r;else p.ReplaceChild(x,r);if(r!=null){r.Parent=p;r.Color=0;}}else if(r==null){if(p==null)Root=l;else p.ReplaceChild(x,l);l.Parent=p;l.Color=0;}else{Node y=MinNode(r);var z=y.RChild;if(y!=r){t=y.Parent;while(t!=x){t.CountSum-=y.Count;t=t.Parent;}y.Parent.LChild=z;if(z!=null)z.Parent=y.Parent;r.Parent=y;y.RChild=r;}y.CountSum=x.CountSum-x.Count;if(l!=null)l.Parent=y;y.LChild=l;if(p==null)Root=y;else p.ReplaceChild(x,y);y.Parent=p;y.Color=x.Color;RemoveFix(z);}x.Count=0;}return;}x=_keyComparer.Compare(k,x.Key)<0?x.LChild:x.RChild;}}[MethodImpl(256)]private void RemoveFix(Node?x){while(true){if(x==null)return;if(x==Root||x.Color==1){x.Color=0;return;}Node p=x.Parent;int dir=p.LChild==x?1:0;var s=dir==0?p.LChild:p.RChild;if(s==null)return;if(s.Color==1){p.Color=1;s.Color=0;Rotate(p,dir^1);continue;}else{Node?sl=dir==1?s.LChild:s.RChild;Node?sr=dir==0?s.LChild:s.RChild;int slc=sl==null?0:sl.Color;int src=sr==null?0:sr.Color;if(slc==0&&src==0){s.Color=1;x=p;continue;}else if(src==0){s.Color=1;sl.Color=0;Rotate(s,dir);x=sl;continue;}else{s.Color=p.Color;p.Color=0;sr.Color=0;Rotate(p,dir^1);return;}}}}} namespace Lib{public partial class StreamScanner{public int[][]ReadUnweightedTree(int n,int origin=1){var gr=new List[n];for(int i=0;i();for(int i=0;i=len){ptr=0;if((len=str.Read(buf,0,1024))<=0){isEof=true;return 0;}}return buf[ptr++];}[MethodImpl(256)]public char Char(){byte b=0;do b=Read();while(b<33||126=33&&b<=126;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public long Integer(){long ret=0;byte b=0;var ng=false;do b=Read();while(b!='-'&&(b<'0'||'9'double.Parse(Scan());}} namespace Lib{public static class OutputLib{[MethodImpl(256)]public static void WriteJoin(string s,IEnumerablet)=>Console.WriteLine(string.Join(s,t));[MethodImpl(256)]public static void WriteMat(T[,]a,string sep=" "){int sz1=a.GetLength(0),sz2=a.GetLength(1);var b=new T[sz2];for(int i=0;i(T[][]a,string sep=" "){for(int i=0;i(T[][]a,Funcmap,string sep=" "){for(int i=0;imap(x)));}[MethodImpl(256)]public static void Write(object t)=>Console.WriteLine(t.ToString());[MethodImpl(256)]public static void Write(params object[]arg)=>Console.WriteLine(string.Join(" ",arg.Select(x=>x.ToString())));[MethodImpl(256)]public static void Write(string str)=>Console.WriteLine(str);[MethodImpl(256)]public static void WriteFlush(object t){Console.WriteLine(t.ToString());Console.Out.Flush();}[MethodImpl(256)]public static void WriteError(object t)=>Console.Error.WriteLine(t.ToString());[MethodImpl(256)]public static void Flush()=>Console.Out.Flush();[MethodImpl(256)]public static void YN(bool t)=>Console.WriteLine(t?"YES":"NO");[MethodImpl(256)]public static void Yn(bool t)=>Console.WriteLine(t?"Yes":"No");[MethodImpl(256)]public static void yn(bool t)=>Console.WriteLine(t?"yes":"no");[MethodImpl(256)]public static void DeleteLine()=>Console.Write("\x1b[1A\x1b[2K");[MethodImpl(256)]public static void ProgressBar(long now,long total,int blocks=50){int x=(int)((2*now*blocks+1)/(2*total));Console.Write($"\x1b[G[\x1b[42m{string.Concat(Enumerable.Repeat("_",x))}\x1b[0m{string.Concat(Enumerable.Repeat("_",blocks-x))}] : {now} / {total}");}}} namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}} #endregion Expanded by https://github.com/kzrnm/SourceExpander