P6398 [COI 2008] KOLEKCIJA

Igor has a playlist containing $n$ songs, numbered from $1$ to $n$. Today he is going to listen to $m$ songs. When playing the $i$-th song, the information of $k$ consecutive songs will be shown in a list. These $k$ consecutive songs must include the $i$-th song, and there are no other requirements. When a song is shown in the list, its information will be read once. If a song is shown in the list multiple times, its information will **only be read once** (no matter whether the two displays are consecutive). Please give a plan that makes the number of songs whose information gets read **as small as possible**.

The first line contains two integers, representing the number of songs in the playlist $n$ and the given parameter $k$. The second line contains one integer, representing the number of songs Igor will listen to, $m$. Lines $3$ to $(m + 2)$ each contain one integer, representing the index $a_i$ of the $i$-th song Igor will listen to.

**This problem uses a Special Judge.** In the first line, output an integer $t$, the minimum number of times song information is read. In lines $2$ to $(m + 1)$, output two integers per line. On line $(i + 1)$, output $l_i, r_i$, meaning that when listening to the $i$-th song, the information of songs from $l_i$ to $r_i$ is displayed. Your output must satisfy $r_i - l_i + 1 = k$, $1 \leq l_i \lt r_i \leq n$, and the number of songs read according to your plan is $t$.

#### Constraints For all test cases, it is guaranteed that: - $1 \leq k \lt n \leq 10^9$, $1 \leq m \leq 3 \times 10^5$. - $1 \leq a_i \leq n$, and all $a_i$ are pairwise distinct. #### Scoring - If the number of output numbers is less than $(2 \cdot m + 1)$, or the number $t$ in the first line is different from the answer, you will get $0\%$ of the score for that test point. - If $t$ is the same as the answer but the output plan is incorrect, you will get $50\%$ of the score for that test point. - If $t$ is the same as the answer and the output plan is correct, you will get $100\%$ of the score for that test point. #### Notes **This problem is translated from [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [COI2008](https://hsin.hr/coci/archive/2007_2008/olympiad_tasks.pdf) *T2 KOLEKCIJA***. The translation and SPJ are provided by [一扶苏一](https://www.luogu.com.cn/user/65363). Translated by ChatGPT 5