დროის ლიმიტი: 4 წმ
მეხსიერების ლიმიტი: 64 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: BULG, შუმენი, 2007, B3
ბუბამ მარცხენა ფეხი იტკინა, ამიტომ ახლა მხოლოდ ცალი ფეხით დახტის. მას სიბრტყეზე მონიშნული ჰქონდა n წერტილი მთელი კოორდინატებით, თუმცა ახლა შეუძლია ისინი მხოლოდ არაკლებადი თანმიმდევრობით გაიაროს. სხვაგვარად რომ ვთქვათ, ბუბას A (x1, y1) წერტილიდან B (x2, y2) წერტილში მისვლა მხოლოდ მაშინ შეუძლია, თუ x1≤x2 და y1≤y2. დაწერეთ პროგრამა, რომელიც გაარკვევს იმ განსხვავებული წერტილების მაქსიმალურ რაოდენობას, რომელთა გავლაც ბუბას შეუძლია.
შესატანი მონაცემები: პირველ სტრიქონში მოცემულია ერთი მთელი რიცხვი n (1≤n≤106). მომდევნო n სტრიქონიდან თითოეულში მოცემულია ორ-ორი მთელი რიცხვი - შესაბამისი წერტილის კოორდინატები. ყველა კოორდინატი არაუარყოფითი მთელი რიცხვია, არაუმეტეს 109-სი.
გამოსატანი მონაცემები: ერთი მთელი რიცხვი - წერტილების რაოდენობა მაქსიმალურად გრძელ გზაზე წერტილთა განმეორების გარეშე.
შესატანი მონაცემები
5 3 2 5 0 0 0 6 1 5 0 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება
ნახტომების თანმიმდევრობაა (0,0)-(5,0)-(6,1) .