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 自动生成