Interval Partition Generator

Let $S = \{1, 2, \ldots, n\}$. For integers $a \le b$, the interval $[a, b]$ is the set of consecutive integers $\{a, a+1, \ldots, b\}$. A partition of $S$ into intervals is a sequence of pairwise disjoint intervals whose union is exactly $S$.

We simulate a generator that builds such a partition step by step. At every moment we keep the set $T$ of elements of $S$ that have not yet been placed into any interval; initially $T = S$. In each iteration we choose one interval that is fully contained in $T$, report it, and remove it from $T$. We repeat until $T$ is empty.

The interval chosen in an iteration is identified by an index. Consider all intervals $[a, b]$ contained in $T$ (that is, every integer from $a$ to $b$ belongs to $T$). Number them from $0$ in lexicographic order by the pair (start, end). For instance, when $T = \{1, 4, 5\}$ the intervals in order are $[1,1]$, $[4,4]$, $[4,5]$, $[5,5]$, receiving indices $0$, $1$, $2$, $3$. The index of the chosen interval is given to your program through the input.

The first line contains one integer $n$ ($1 \le n \le 1000000$).

The remaining input lists the chosen indices, one per iteration, in order. Starting from $T = \{1, 2, \ldots, n\}$, repeat the following while $T$ is not empty:

• Let $L$ be the number of intervals contained in the current $T$.
• Read one integer $l$ ($0 \le l < L$), the index of the chosen interval.
• Remove the interval with index $l$ from $T$.

The given indices are exactly enough to empty $T$: it becomes empty right after the last index is used.

For each iteration, in order, print two lines:

• a line with $L$, the number of intervals contained in $T$ at the start of that iteration;
• a line with two integers $a$ and $b$ separated by a single space, the endpoints of the chosen interval $[a, b]$.