4348: 「JOI 2017 Final」绳
内存限制：256 MB
时间限制：2.500 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
**题目译自 [JOI 2017 Final](https://www.ioi-jp.org/joi/2016/2017-ho/) T5「[縄](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho.pdf) / [Rope](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho-en.pdf)」**
JOI 小宝宝正拿着一根绳子玩。绳子可视为一条长度为 $N$ 的左右延伸的线段。绳子由 $N$ 根线连接而成，每根线的长度为 $1$，厚度为 $1$。绳子上的线共有 $M$ 种颜色，左数第 $i$ 根线 $(1\leqslant i\leqslant N)$ 的颜色为 $C_i(1\leqslant C_i\leqslant M)$。**绳子的左端点**意为左数第 $1$ 根线的左端点，**绳子的右端点**意为右数第 $1$ 根线的右端点。显然左数第 $i$ 根线 $(1\leqslant i\leqslant N)$ 的右端点 到 绳子的左端点 的距离为 $i$。
JOI 把绳子的长度缩短了。具体来说，JOI 反复地进行以下过程，直到绳长缩短至 $2$。
* 假设此时绳子的长度为 $L$。指定一个整数 $j(1\leqslant j \cfrac{L}{2}$，则将左数第 $i$ 根线 $(2j-L+1\leqslant i\leqslant j)$ 与左数第 $(2j-i+1)$ 根线拧成一股。此时，绳子原本的左端点变为右端点，绳长变为 $j$。
* 两条线的颜色相同才能拧成一股。在将两条线拧成一股前，可以任意改变线的颜色。将线染成其他颜色所需的费用 等于 线的厚度。颜色匹配后，两条线将被拧成一股，新的一股线的厚度 将为 两条线的厚度之和。
我们把绳长缩短至 $2$ 的绳子称为最终的绳子。JOI 希望使得将绳长缩短至 $2$ 所需的费用尽可能小。对于每种颜色，JOI 都想知道，在最终的绳子中包含这种颜色的情况下，将绳长缩短至 $2$ 所需的最小费用。
你的任务是帮 JOI 解决这个问题。
输入
第一行有两个整数 $N, M$，用空格分隔。
第二行有 $N$ 个用空格分隔的整数 $C_1, C_2, \ldots, C_N$。
输入的所有数的含义见题目描述。
输出
共 $M$ 行，第 $c$ 行 $(1\leqslant c\leqslant M)$ 有一个整数，表示在最终的绳子中包含颜色 $c$ 的情况下，将绳长缩短至 $2$ 所需的最小费用。
样例输入 复制
5 3
1 2 3 3 2样例输出 复制
2
1
1提示
输入样例2
7 3 1 2 2 1 3 3 3
输出样例2
2 2 2
输入样例3
10 3 2 2 1 1 3 3 2 1 1 2
输出样例3
3 3 4
数据范围：对于 $15\%$ 的数据，$N\leqslant 15, M\leqslant 10$。 对于另外 $30\%$ 的数据，$N\leqslant 10^5, M\leqslant 10$。 对于另外 $10\%$ 的数据，$N\leqslant 10^5, M\leqslant 500$。 对于另外 $25\%$ 的数据，$M\leqslant 5000$。 对于所有数据，$2\leqslant N\leqslant 10^6, 1\leqslant M\leqslant N, 1\leqslant C_i\leqslant M(1\leqslant i\leqslant N)$，在初始状态的绳子上，颜色 $1, 2, \ldots, M$ 都至少出现了一次。