თივის შეკვრების დალაგება

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

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

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

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

წყარო: USACO, 2011/12, JAN, BRONZE


უკანასკნელ ხანებში ფერმის მიმართ გაზრდილი საშიშროებებით შეწუხებული ბესიმ გადაწყვიტა, რომ ფერმერ ჯონს დაეხმაროს შემოსასვლელის წინ თივის შეკვრების დაწყობაში. მან უნდა დააწყოს შეკვრების დასტები N (1 <= N <= 1,000,000, N კენტია) ადგილზე, რომლებიც გადანომრილია 1..N. ფერმერი ჯონი მას აძლევს K ცალი (1 <= K <= 25,000) ბრძანებისაგან შედგენილ მიმდევრობას "A B" ფორმატით, რაც ნიშნავს, რომ ბესიმ თითო შეკვრა უნდა დაამატოს იმ დასტებს, რომლებიც დევს ადგილებზე, რომელთა ნომრები არის დიაპაზონში A..B. მაგალითად, ბრძანებაზე "10 13", ბესიმ იცის, რომ თითო შეკვრა უნდა დაამატოს იმ დასტებს, რომლებიც განთავსებულია ადგილებზე 10, 11, 12, და 13.

მას შემდეგ, რაც ბესი დაამთავრებს ბრძანებათა მიმდევრობის შესრულებას, ფერმერ ჯონს უნდა, რომ გაიგოს არსებული N დასტის მედიანის სიმაღლე - ანუ ეს დასტები რომ სიმაღლის მიხედვით დავაწყოთ, შუა დასტის სიმაღლე. რადგან N კენტია, შუა დასტა ყოველთვის ერთადერთია. დაეხმარეთ ბესის, რომ ჯონის შეკითხვას სწორად გასცეს პასუხი.

შეტანის ფორმატი: სტრიქონი 1: ჰარით გამოყოფილი ორი მთელი რიცხვი N და K.

სტრიქონები 2..1+K: თითოეული სტრიქონი შეიცავს FJ- მორიგ ბრძანებას ჰარით გამოყოფილი ორი მთელ რიცხვს A და B (1 <= A <= B <= N).

გამოტანის ფორმატი: ერთადერთ სტრიქონში გამოიტანეთ მედიანის სიმაღლე მას შემდეგ, რაც ბესი დაამთავრებს ბრძანებების შესრულებას.

 




მაგალითები

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

შენიშვნა

შეტანის განმარტებასულ არის N=7 დასტის დასაწყობი ადგილი და FJ იძლევა K=4 ბრძანებასპირველი ბრძანება ნიშნავსრომ ერთი შეკვრა უნდა დაიდოს მე-5 ადგილზემეორე ბრძანებით თითო შეკვრა უნდა დაიდოს ადგილებზე 2..4 და ..

                                          გამოტანის განმარტებამას შემდეგრაც ბესი დაამთავრებსდასტების სიმაღლეები იქნება 0,1,2,3,3,1,0. მედიანის სიმაღლეა 1, ვინაიდან 1 არის ზრდადობით დალაგებული მიმდევრობის შუა წევრი 0,0,1,1,2,3,3.