P5923 [IOI 2004] empodia Obstacle Segments

The ancient mathematician and philosopher Pythagoras believed that the essence of nature is mathematics. Modern biologists study biological sequences.

A biological sequence is a sequence of $M$ integers that satisfies the following conditions: - It contains all numbers in $0, 1, \cdots, M-1$. - The first number is $0$, and the last number is $M - 1$. - In the sequence, $E+1$ cannot appear immediately after $E$. A contiguous subsequence of a biological sequence is called a segment. If a segment satisfies: - Its starting element is the smallest number in the segment. - Its ending element is the largest number in the segment, and it is not the same number as the starting element. - All integers between these two numbers appear in this segment. then this segment is called an empodio segment. If an empodio segment does not contain any shorter empodio segment, it is called an obstacle segment. For example, consider the biological sequence `(0,3,5,4,6,2,1,7)`. The entire sequence is an empodio segment, but it contains another empodio segment `(3,5,4,6)`, so the entire sequence is not an obstacle segment. The empodio segment `(3,5,4,6)` does not contain any shorter empodio segment, so it is an obstacle segment, and it is the only obstacle segment in this biological sequence. Please write a program that, given a biological sequence, outputs all obstacle segments.

The first line contains a single integer $M$, representing the length of the biological sequence. The numbers in the biological sequence appear in order in the next $M$ lines, one integer per line.

The first line contains an integer $H$, representing the number of obstacle segments in the biological sequence. The next $H$ lines output each obstacle segment in order of the starting position in the original input biological sequence. Each line contains two integers $A$ and $B$, separated by a single space. The $A$-th element of the original input biological sequence is the start of this obstacle segment, and the $B$-th element is the end of this obstacle segment.

For $100\%$ of the testdata, $M \le 1100000$. Translated by ChatGPT 5