Problem : 255 - Empodia

Problem Statistics

Solved Member: 14　　Submission: 115　　User Tried: 17

Statement:

古數學及哲學家畢氏相信自然之本質為數學。現代生物學家研究生物數列(biosequences)。生物數列為滿足下列條件之 M 個整數所成的數列：
　• 包含從 0, 1, …, 到 M – 1 的所有數字
　• 起始數字為 0，最後一個數字為 M – 1
　• 數列中 E+1 不可以緊接在 E 之後
生物數列的連續子數列稱為數段(segments)。

如果一個數段的起點為該數段最小的數字，終點為該數段最大的數字且與起點不是同一個數字，且介於這兩個數字之間所有的整數都出現在這個數段中，則稱這個數段為框段(framed interval)，如果框段中並不包含更小的框段，則稱之為障礙段(empodio)。

以(0,3,5,4,6,2,1,7)這個生物數列為例。整個生物數列是一個框段，可是它包含了另外一框段 (3,5,4,6) ，因此該生物數列不是障礙段。而框段 (3,5,4,6) 並不包含任何更短的框段所以它是一個障礙段，而且是此生物數列中唯一的障礙段。

請寫一個程式，在輸入生物數列後，輸出所有的障礙段 (empodia 為 empodio的複數形)。

Input:Output:

第一行為單一整數 M，代表生物數列的長度。生物數列中的數字依序出現在接下來的 M 行，每一行有一個整數。

第一行為一整數H，代表該生物數列中的障礙段的個數。

接下來的H 行，將每一個障礙段，依照起點在原輸入生物數列中出現的順序，依序輸出。每行以兩個整數A 與B 代表一個障礙段並以一個空白分開，原輸入生物數列第 A 個元素為該障礙段之起點，而第 B 個元素為該障礙段之終點。

其中一組測試資料 1000000 ≤ M ≤ 1100000。除了前面這一組測試資料外，在其他所有的測試資料裡，1 ≤ M ≤ 60000。此外有50%的測試資料裡，M ≤ 2600。

Sample Input:Sample Output:

8
0
3
5
4
6
2
1
7

1
2 5

Source:

IOI 2004

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	131072kb
1	1000ms	131072kb	5
2	1000ms	131072kb	5
3	1000ms	131072kb	5
4	1000ms	131072kb	5
5	1000ms	131072kb	5
6	1000ms	131072kb	5
7	1000ms	131072kb	5
8	1000ms	131072kb	5
9	1000ms	131072kb	5
10	1000ms	131072kb	5
11	1000ms	131072kb	5
12	1000ms	131072kb	5
13	1000ms	131072kb	5
14	1000ms	131072kb	5
15	1000ms	131072kb	5
16	1000ms	131072kb	5
17	1000ms	131072kb	5
18	1000ms	131072kb	5
19	1000ms	131072kb	5
20	1000ms	131072kb	5