ქოლგები

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

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

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

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

წყარო: USACO, 2003/04, DEC, GREEN


კოკისპირულად წვიმს. ძროხები, რომელთაც სიმშრალეში სურთ ბალახობა, შეიკრიბნენ N (1<=N<=25000) ქოლგის ქვეშ. საძოვარი წარმოადგენს ერთიან ბალახოვან მონაკვეთს. ყოველი ქოლგა მთლიანად ფარავს საძოვრის გარკვეულ ფრაგმენტს, თუმცა ძროხებმა ქოლგები იმგვარად განალაგეს, რომ მათ მიერ დაფარული ფრაგმენტები შეიძლება რამდენჯერმე გადაიფარონ. თქვენი ამოცანაა მოძებნოთ ისეთი ქოლგების უდიდესი რაოდენობა, რომლებიც ერთი ქოლგით არიან დაფარულები.

შემავალი მონაცემების ფორმატი: 1 სტრიქონი: მოცემულია მთელი N რიცხვი; 2..N+1 სტრიქონებში: მთელი A და B (1<=A<B<=2 000 000 000) რიცხვები, რომლებიც წარმოადგენენ ქოლგით დაფარულ საძოვრის ინტერვალებს. ქოლგათა არცერთ წყვილს არ გააჩნია საერთო სასაზღვრო წერტილი.

გამომავალი მონაცემების ფორმატი: ერთადერთ სტრიქონში ნაჩვენები უნდა იყოს ერთადერთი მთელი რიცხვი – იმ ქოლგების მაქსიმალური რაოდენობა, რომლებიც ერთი ქოლგით არიან დაფარულები.




მაგალითები

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

შენიშვნა

განმარტება: პირველი ქოლგა ფარავს მეორე და მესამე ქოლგებს.