Empodia

Time limit1sMemory limit128 MB

Summary

Given a permutation biosequence, find every minimal framed interval: a segment whose endpoints are its min and max and that contains no shorter framed interval.

Level: Hard8 of 10
Topics: Stack, Array, Implementation, Greedy
Solved: No attempts yet

Problem

Biologists study biosequences. A biosequence is a sequence of $M$ integers that

contains each of the numbers $0, 1, \dots, M-1$ exactly once,
starts with $0$ and ends with $M-1$ , and
never has two values $E$ and $E+1$ next to each other in that order (an element is never immediately followed by its successor).

A contiguous block of a biosequence is called a segment.

A segment is a framed interval if its first element is the smallest value of the segment, its last element is the largest value of the segment (and different from the first), and the segment contains every integer whose value lies between the first and the last. Equivalently, the segment from position $i$ to position $j$ is a framed interval when its first element is the minimum, its last element is the maximum, and the values it covers are exactly the consecutive integers from that minimum up to that maximum.

A framed interval is an empodio if it contains no shorter framed interval.

For example, in the biosequence $(0, 3, 5, 4, 6, 2, 1, 7)$ the whole sequence is a framed interval, but it is not an empodio because it contains the shorter framed interval $(3, 5, 4, 6)$ . That inner framed interval contains no shorter framed interval, so it is an empodio, and it is the only empodio of this biosequence.

Given a biosequence, find all of its empodia (the plural of empodio).

Input

The first line contains one integer $M$ , the number of elements of the biosequence. Each of the next $M$ lines contains one integer; taken in order, these integers form the biosequence.

Output

On the first line print one integer $H$ , the number of empodia in the biosequence. Then print $H$ lines describing the empodia in increasing order of their starting position. Each line contains two integers $A$ and $B$ separated by a single space, meaning that the empodio starts at the $A$ -th element and ends at the $B$ -th element of the biosequence. Positions are numbered from $1$ .

Constraints

In exactly one of the inputs, $1000000 \le M \le 1100000$ . In every other input, $1 \le M \le 60000$ .

Examples4

Example 1
Input
```
8
0
3
5
4
6
2
1
7
```
Expected output
```
1
2 5
```
Example 2
Input
```
4
0
2
1
3
```
Expected output
```
1
1 4
```
Example 3
Input
```
11
0
2
1
3
9
8
7
4
6
5
10
```
Expected output
```
2
1 4
4 11
```
Example 4
Input
```
10
0
2
1
3
5
4
6
8
7
9
```
Expected output
```
3
1 4
4 7
7 10
```