구간 분할 생성기

집합 $S = \{1, 2, \ldots, n\}$이 주어진다. 정수 $a \le b$에 대해 구간 $[a, b]$는 연속한 정수의 집합 $\{a, a+1, \ldots, b\}$를 뜻한다. $S$를 구간들로 분할한다는 것은, 서로소인 구간들의 수열로서 그 합집합이 정확히 $S$가 되도록 만드는 것이다.

이러한 분할을 한 단계씩 만들어 내는 생성기를 시뮬레이션한다. 매 순간, 아직 어떤 구간에도 포함되지 않은 $S$의 원소들의 집합 $T$를 유지한다. 처음에는 $T = S$이다. 각 반복에서 $T$에 완전히 포함되는 구간 하나를 골라 출력한 뒤 $T$에서 제거한다. $T$가 공집합이 될 때까지 이를 반복한다.

각 반복에서 고르는 구간은 번호로 지정된다. $T$에 포함되는 모든 구간 $[a, b]$(즉 $a$부터 $b$까지의 모든 정수가 $T$에 속하는 구간)를 생각하자. 이들을 (시작점, 끝점) 쌍에 대한 사전식 순서로 $0$번부터 번호를 매긴다. 예를 들어 $T = \{1, 4, 5\}$일 때 구간들은 순서대로 $[1,1]$, $[4,4]$, $[4,5]$, $[5,5]$이며 각각 번호 $0$, $1$, $2$, $3$을 가진다. 고른 구간의 번호는 입력으로 주어진다.

첫째 줄에 정수 $n$ ($1 \le n \le 1000000$)이 주어진다.

이어지는 입력에는 각 반복에서 고른 구간의 번호가 순서대로 하나씩 주어진다. $T = \{1, 2, \ldots, n\}$에서 시작하여 $T$가 공집합이 아닌 동안 다음을 반복한다.

• 현재 $T$에 포함되는 구간의 개수를 $L$이라 한다.
• 정수 $l$ ($0 \le l < L$), 즉 고른 구간의 번호를 읽는다.
• 번호가 $l$인 구간을 $T$에서 제거한다.

주어지는 번호들은 $T$를 정확히 비우기에 딱 맞는 개수이며, 마지막 번호를 사용한 직후 $T$는 공집합이 된다.

각 반복마다 순서대로 두 줄을 출력한다.

• 그 반복을 시작할 때 $T$에 포함되는 구간의 개수 $L$을 한 줄에 출력한다.
• 고른 구간 $[a, b]$의 양 끝점 $a$와 $b$를 공백 하나로 구분하여 한 줄에 출력한다.