One (simplified) programming problem from the recent Asia-Pacific Informatics Olympiad 2009 competition The Siruseri Convention Centre The Government of Siruseri has constructed a new Convention Centre. A number of companies have expressed an interest in renting the auditorium in the Convention Centre to hold their conferences. A client is willing to rent the auditorium only if it is granted to him exclusively for the entire duration of his conference. The marketing head of the Convention Centre has decided that the best strategy would be to rent the auditorium out to as many different clients as possible. Clearly there may be more than one way to do this. Consider, for instance, the following example with 4 companies. The companies are listed in the order in which they made requests for the audi- torium, with the duration of each conference indicated by the starting and ending day. Start End Company 1 4 9 Company 2 9 11 Company 3 13 19 Company 4 10 17 In this example, it is possible to rent out the auditorium to a maximum of two companies. The choices are 1 and 3, or 2 and 3, or 1 and 4. Note that the auditorium can be rented out to only one company on any day. Thus, 1 and 2 cannot both be granted the auditorium because their requests overlap. A set of requests is a candidate to be chosen if it is of maximum size. Your task is to help the marketing head decide the set of companies to which the auditorium is to be rented. Limits / Constraints: In 50% of the inputs, N <= 3000. In all inputs, N <= 200000. For each company's request, the starting day is always greater than or equal to 1 and the ending day never exceeds 10^9.