თანაუკვეთი ინტერვალები

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


მოცემულია N ცალი ინტერვალი, რომლებიც ერთ წრფეზე არიან განლაგებული. დაწერეთ პროგრამა, რომელიც გამოითვლის იმ ინტერვალთა მაქსიმალურ რაოდენობას, რომელიც ერთმანეთს არ ჰკვეთენ. თვლიან, რომ ორი ინტერვალი იკვეთება, თუ მათ ერთზე მეტი საერთო წერტილი აქვთ.

შემოსატანი მონაცემები" პირველ სტრიქონში ერთი მთელი რიცხვი N (1<N<=1000000). მომდევნო N სტრიქონიდან თითოეულში ორ-ორი მთელი რიცხვი - ინტერვალთა საზღვრები, რომლებიც მოტავსებულია დიაპაზონში 1...2000000.

გამოსატანი მონაცემები: იმ ინტერვალთა მაქსიმალურ რაოდენობა, რომელიც ერთმანეთს არ ჰკვეთენ




მაგალითები

შესატანი მონაცემები
5 7 9 3 5 6 9 1 3 1 8 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება