P6398 [COI 2008] KOLEKCIJA

Igor 有一个包含 $n$ 首歌的歌单，歌曲从 $1$ 至 $n$ 编号，他今天要听 $m$ 首歌。 当播放第 $i$ 首歌时，连续 $k$ 首歌的信息会被显示在一个列表上，这连续 $k$ 首歌必须包含第 $i$ 首歌，但是没有其他要求。 当一首歌被显示在列表上时，它的信息会被读取一次。如果一首歌多次被显示在列表上，他的信息也**只会被读取一次**（无论两次显示是否连续）。 请给出一种方案，使得系统读取歌曲信息的次数**最少**。

第一行有两个整数，分别表示歌单的歌曲数 $n$ 和给定的参数 $k$。 第二行有一个整数，表示 Igor 要听的歌曲数 $m$。 第 $3$ 到第 $(m + 2)$ 行，每行一个整数，表示 Igor 要听的第 $i$ 首歌的编号 $a_i$。

**本题存在 Special Judge**。 请在第一行输出一个整数 $t$，表示读取歌曲信息的最少次数。 第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的 $l_i, r_i$，表示听第 $i$ 首歌的时候显示第 $l_i$ 到第 $r_i$ 首歌的信息。 你的输出需要保证 $r_i - l_i + 1 = k$，$1 \leq l_i \lt r_i \leq n$，且按照你给出的方案读取的歌曲数为 $t$。

#### 数据规模与约定 对于全部的测试点，保证： - $1 \leq k \lt n \leq 10^9$，$1 \leq m \leq 3 \times 10^5$。 - $1 \leq a_i \leq n$，$a_i$ 互不相同。 #### 计分标准 - 如果输出的数字不足 $(2 \cdot m + 1)$ 个，或输出第一行的数字 $t$ 与答案不同，则获得测试点 $0\%$ 的分数。 - 如果 $t$ 与答案相同，输出方案错误，则获得该测试点 $50\%$ 的分数。 - 如果 $t$ 与答案相同，且输出方案正确，则获得该测试点 $100\%$ 的分数。 #### 说明 **题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [COI2008](https://hsin.hr/coci/archive/2007_2008/olympiad_tasks.pdf) *T2 KOLEKCIJA***，翻译与 SPJ 均来自[一扶苏一](https://www.luogu.com.cn/user/65363)。