Empodia

생물학자들은 생물열(biosequence) 을 연구한다. 생물열이란 다음 조건을 모두 만족하는 $M$개의 정수로 이루어진 수열이다.

• $0, 1, \dots, M-1$ 을 각각 정확히 한 번씩 포함한다.
• $0$ 으로 시작하고 $M-1$ 로 끝난다.
• 어떤 값 $E$ 바로 뒤에 그 값보다 $1$ 큰 값 $E+1$ 이 오는 일이 없다. 즉, 이웃한 두 원소가 이 순서대로 $E, E+1$ 이 되는 경우가 없다.

생물열에서 연속한 원소들로 이루어진 부분을 구간(segment) 이라 한다.

어떤 구간의 첫 원소가 그 구간의 최솟값이고, 마지막 원소가 그 구간의 최댓값(이며 첫 원소와 다른 값)이며, 첫 값과 마지막 값 사이의 모든 정수를 그 구간이 포함할 때, 그 구간을 테두리 구간(framed interval) 이라 한다. 바꿔 말하면, 위치 $i$ 부터 위치 $j$ 까지의 구간이 테두리 구간이라는 것은 첫 원소가 최솟값, 마지막 원소가 최댓값이고, 구간이 담고 있는 값들이 그 최솟값부터 최댓값까지의 연속한 정수 전체와 정확히 일치한다는 뜻이다.

테두리 구간이 자신보다 짧은 테두리 구간을 하나도 포함하지 않으면, 그 구간을 엠포디오(empodio) 라 한다.

예를 들어 생물열 $(0, 3, 5, 4, 6, 2, 1, 7)$ 에서 수열 전체는 테두리 구간이지만, 더 짧은 테두리 구간 $(3, 5, 4, 6)$ 을 포함하므로 엠포디오가 아니다. 반면 $(3, 5, 4, 6)$ 은 자신보다 짧은 테두리 구간을 포함하지 않으므로 엠포디오이며, 이 생물열의 유일한 엠포디오이다.

생물열이 주어질 때, 그 안의 모든 엠포디아(empodia, empodio의 복수형)를 찾아라.

첫째 줄에 생물열의 원소 개수인 정수 $M$ 이 주어진다. 이어지는 $M$ 개의 줄에는 각 줄마다 정수가 하나씩 주어지며, 이 정수들이 순서대로 생물열을 이룬다.

첫째 줄에 생물열에 들어 있는 엠포디아의 개수 $H$ 를 출력한다. 그다음 $H$ 개의 줄에 각 엠포디오를 시작 위치가 앞선 순서대로 출력한다. 각 줄에는 두 정수 $A$ 와 $B$ 를 공백 하나로 구분하여 출력하며, 이는 해당 엠포디오가 생물열의 $A$ 번째 원소에서 시작하여 $B$ 번째 원소에서 끝난다는 뜻이다. 위치는 $1$ 부터 센다.

입력 중 정확히 하나에서는 $1000000 \le M \le 1100000$ 이다. 그 외의 모든 입력에서는 $1 \le M \le 60000$ 이다.