AT_joi2017ho_e 縄 (Rope)

现有一条由 $N$ 根细绳组成的绳子，这些细绳的颜色有 $M$ 种。你的任务是编写一个程序，计算出每种颜色在绳子长度为 $2$ 且包含该颜色时所需的最小成本。

标准输入包含以下数据： - 第 1 行是两个用空格分隔的整数 $N$ 和 $M$，表示有 $N$ 根细绳和 $M$ 种颜色。 - 第 2 行包含 $N$ 个整数 $C_1, C_2, \ldots, C_N$，其中 $C_i$ 表示从左到右第 $i$ 根细绳的颜色。

针对每种颜色，输出共 $M$ 行。第 $c$ 行（$1 \leq c \leq M$）输出绳子包含颜色 $c$ 且长度为 $2$ 的最小成本。

### 任务要求 根据给定的细绳颜色，计算出使得绳子包含指定颜色并且长度为 $2$ 时所需的最小成本。 ### 限制条件 所有输入数据需满足以下条件： - $2 \leq N \leq 1\,000\,000$。 - $1 \leq M \leq N$。 - $1 \leq C_i \leq M$（$1 \leq i \leq N$）。 - 对于每个颜色 $c$（$1 \leq c \leq M$），都至少存在一个 $i$ 使得 $C_i = c$。 ### 子任务 #### 子任务 1 [15 分] 满足以下条件： - $N \leq 15$。 - $M \leq 10$。 #### 子任务 2 [30 分] 满足以下条件： - $N \leq 100\,000$。 - $M \leq 10$。 #### 子任务 3 [10 分] 满足以下条件： - $N \leq 100\,000$。 - $M \leq 500$。 #### 子任务 4 [25 分] 满足以下条件： - $M \leq 5\,000$。 #### 子任务 5 [20 分] 没有额外的限制。 ### 示例解释 1 可以通过以下操作，以 2 的成本使绳子包含颜色 1 并且长度为 2： - 将第 2 根细绳涂成颜色 1，并将其与右边的细绳合并。此时绳子的颜色顺序为 $1, 3, 3, 2$，厚度顺序为 $2, 1, 1, 1$。 - 将第 4 根细绳涂成颜色 1，并进行合并。此时绳子的颜色顺序为 $3, 1$，以及厚度为 $2, 3$。 同样，可以通过以下操作，以成本 1 使绳子包含颜色 2 和 3 且长度为 2： - 第 3 根细绳涂成颜色 2，并进行合并。最终颜色顺序为 $2, 3$，厚度为 $3, 2$。 ### 示例解释 2 可以通过以下操作，以 2 的成本使绳子包含颜色 1 并且长度为 2： - 在第 1 根细绳上涂色为 1，然后合并。注意，由于此处细绳的厚度为 2，因此费用为 2。 - 将第 3 根细绳直接合并，最终顺序为 $2, 3$，厚度为 $3, 2$。 ### 示例解释 3 进行一次合并之前，允许对多个细绳进行涂色调整。 **本翻译由 AI 自动生成**