TopCoder

Thumb kirino9
dreamoon
桐乃是最強的!

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

11.1% (1/9)

Description

Siruseri 政府建造了一座新的會議中心。
許多公司對租借會議中心的會堂很感興趣,他們希望能夠在裏面舉行會議。
對於一個客戶而言,僅當在開會時能夠獨自佔用整個會堂,他才會租借會堂。
會議中心的銷售主管認為:最好的策略應該是將會堂租借給盡可能多的客戶。
顯然,有可能存在不止一種滿足要求的策略。
例如下面的例子。總共有 4 個公司。
他們對租借會堂發出了請求,並提出了他們所需佔用會堂的起止日期(如下表所示)。

開始日期結束日期
公司 149
公司 2911
公司 31319
公司 41017

上例中,最多將會堂租借給兩家公司。
租借策略分別是租給公司1和公司3,或是公司2和公司3,也可以是公司1和公司4。
注意會議中心一天最多租借給一個公司,所以公司1和公司2不能同時租借會議中心,因為他們在第九天重合了。

銷售主管為了公平起見,決定按照如下的程式來確定選擇何種租借策略:
首先,將租借給客戶數量最多的策略作為候選,將所有的公司按照他們發出請求的順序編號。
對於候選策略,將策略中的每家公司的編號按昇冪排列。
最後,選出其中字典序最小1的候選策略作為最終的策略。

例中,會堂最終將被租借給公司1和公司3:
三個候選策略是{(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)<(2,3)。
你的任務是幫助銷售主管確定應該將會堂租借給哪些公司。

1字典序指在字典中排列的順序,如果序列l1是序列l2的前綴,或者對於l1l2的第一個不同位置j,l1[j]<l2[j],則l1比l2小。

Input Format

輸入的第一行有一個整數 N,表示發出租借會堂申請的公司的個數。
第 2 到第 N+1 行每行有 2 個整數。
第 i+1 行的整數表示第 i 家公司申請租借的起始和終止日期。
對於每個公司的申請,起始日期為不小於 1 的整數,終止日期為不大於109的整數。

對於 50%的輸入,N≤3000。在所有輸入中,N≤200000

Output Format

輸出的第一行應有一個整數 M,表示最多可以租借給多少家公司。
第二行應列出 M 個數,表示最終將會堂租借給哪些公司。

Sample Input

4
4 9
9 11
13 19
10 17

Sample Output

2
1 3

Hints

Problem Source

原TIOJ1743 / APIO '09

Subtasks

For Testdata: 0 ~ 0, Score: 4
For Testdata: 1 ~ 1, Score: 4
For Testdata: 2 ~ 2, Score: 4
For Testdata: 3 ~ 3, Score: 4
For Testdata: 4 ~ 4, Score: 4
For Testdata: 5 ~ 5, Score: 4
For Testdata: 6 ~ 6, Score: 4
For Testdata: 7 ~ 7, Score: 4
For Testdata: 8 ~ 8, Score: 4
For Testdata: 9 ~ 9, Score: 4
For Testdata: 10 ~ 10, Score: 4
For Testdata: 11 ~ 11, Score: 4
For Testdata: 12 ~ 12, Score: 4
For Testdata: 13 ~ 13, Score: 4
For Testdata: 14 ~ 14, Score: 4
For Testdata: 15 ~ 15, Score: 4
For Testdata: 16 ~ 16, Score: 4
For Testdata: 17 ~ 17, Score: 4
For Testdata: 18 ~ 18, Score: 4
For Testdata: 19 ~ 19, Score: 4
For Testdata: 20 ~ 20, Score: 4
For Testdata: 21 ~ 21, Score: 4
For Testdata: 22 ~ 22, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 15000 65536 65536
1 15000 65536 65536
2 15000 65536 65536
3 15000 65536 65536
4 15000 65536 65536
5 15000 65536 65536
6 15000 65536 65536
7 15000 65536 65536
8 15000 65536 65536
9 15000 65536 65536
10 15000 65536 65536
11 15000 65536 65536
12 15000 65536 65536
13 15000 65536 65536
14 15000 65536 65536
15 15000 65536 65536
16 15000 65536 65536
17 15000 65536 65536
18 15000 65536 65536
19 15000 65536 65536
20 15000 65536 65536
21 15000 65536 65536
22 15000 65536 65536