2336 「JOI 2017 Final」绳

题目译自 JOI 2017 Final T5「縄 / Rope」

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<L)$，使绳子左数第 $j$ 根线成为绳子的左端点（最左的线），并折叠绳子。也就是说，
• 如果 $j\leqslant \cfrac{L}{2}$，则将左数第 $i$ 根线 $(1\leqslant i\leqslant j)$ 与左数第 $(2j-i+1)$ 根线拧成一股。此时，绳子原本的右端点仍是右端点，绳长变为 $L-j$。
• 如果 $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$ 所需的最小费用。

通过下述步骤，只需花费 $2$，就可以使得最终的绳子中包含颜色 $1$。 * 把左数第 $2$ 根线染成颜色 $1$。折叠绳子使得 原本到左端点的距离为 $1$ 的端点 变为 新的左端点。现在，从左往右数，线的颜色依次是 $1,$ $ 3,$ $ 3,$ $ 2$，厚度依次是 $2,$ $ 1,$ $ 1,$ $ 1$。 * 把左数第 $4$ 根线染成颜色 $1$。折叠绳子使得 原本到左端点的距离为 $2$ 的端点 变为 新的左端点。现在，从左往右数，线的颜色依次是 $3, 1$，厚度依次是 $2, 3$。

通过下述步骤，只需花费 $1$，就可以使得最终的绳子中包含颜色 $2$ 和 $3$。 * 折叠绳子使得 原本到左端点的距离为 $3$ 的端点 变为 新的左端点。现在，从左往右数，线的颜色依次是 $3,$ $ 2,$ $ 1$，厚度依次是 $2,$ $ 2,$ $ 1$。 * 把左数第 $3$ 根线染成颜色 $2$。折叠绳子使得 原本到左端点的距离为 $2$ 的端点 变为 新的左端点。现在，从左往右数，线的颜色依次是 $2, 3$，厚度依次是 $3, 2$。

通过下述步骤，只需花费 $2$，就可以使得最终的绳子中包含颜色 $1$。 * 折叠绳子使得 原本到左端点的距离为 $2$ 的端点 变为 新的左端点。 * 把左数第 $1$ 根线染成颜色 $1$。折叠绳子使得 原本到左端点的距离为 $1$ 的端点 变为 新的左端点。注意这次染色的费用为 $2$，因为此时左数第 $1$ 根线的厚度为 $2$。 * 折叠绳子使得 原本到左端点的距离为 $3$ 的端点 变为 新的左端点。 * 折叠绳子使得 原本到左端点的距离为 $1$ 的端点 变为 新的左端点。

对于 $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$ 都至少出现了一次。