配点: 100 点
宝贝 JOI 正在玩绳子。绳子的长度是 N 并从一侧直线延伸到另一侧。绳子很粗 1,长度 1 的字符串 N 它由连接的部分组成。在绳子上 M 使用不同的颜色,从左侧开始: i 字符串的颜色是 C_i (1 \leqq C_i \leqq M)。
JOI君把绳子扭在一起,让它变短。具体而言,根据绳索的长度进行以下操作。 重复直到 2 。
- 绳子的长度 L 。某个整数 j (1 \leqq j < L) 和从左边开始的长度
将绳子扭在一起,使 j 的位置成为新的左端点。也就是说,
当
- j \leqq L/2 时,每个 i (1 \leqq i \leqq j) 从左开始 从左起第 i 串 扭动第 2j - i + 1 根绳子。此时,原来为右端点的位置继续为右端点,绳子的长度为 L - j 变为。
- j > L/2 时,每个 i (2j - L + 1 \leqq i \leqq j) 从左开始 从左起第 i 串 扭动第 2j - i + 1 根绳子。此时,原来为左端点的位置变成了右端点,绳子的长度为 j 变为。
- 此时,每组绞线的颜色必须相同。琴弦在绞合在一起之前可以重新涂成任何颜色,但重新涂漆的成本与厚度相同。颜色匹配后,将绳子扭在一起,所得绳子的粗细也扭在一起。 2 它是两根弦的粗细之和。
JOI君有一条很长的绳子。 我们希望最大限度地减少 2 之前执行的操作的总成本。 JOI 希望在执行操作时找到所有颜色的最小成本总和,以便最终的绳子包含该颜色。
你的工作就是代表JOI君解决这个问题。
課題
给定构成第一根绳子的绳子的颜色,对于每种颜色,找到包含该颜色且具有长度的绳子。 编写一个程序来找出获得 2 所需的最低成本。
入力
从标准输入读取以下输入。
- 1 在线 2 整数 给出了 N, M 以空格作为分隔符。这些是构成绳子的绳子。 N 和它们的颜色是 M 表示有不同类型。
- 2 在线 N 整数 给出了 C_1, C_2, \ldots,C_N 以空格作为分隔符。这些是从左边开始的 i 字符串的颜色是 C_i 。
出力
到标准输出 输出 M 行输出。M 行 c (1 \leqq c \leqq M) 线显示绳索的最终长度。 2 并且绳子有颜色。 c 调整成本总和的最小值以包括 1 行输出。
制限
所有输入数据满足以下条件。
- 2 \leqq N \leqq 1\,000\,000.
- 1 \leqq M \leqq N.
- 1 \leqq C_i \leqq M (1 \leqq i \leqq N).
- 1 \leqq c \leqq M 的整数 c ,C_i = c 变为 i 存在。
小課題
小課題 1 [15 点]
满足以下条件。
- N \leqq 15.
- M \leqq 10.
小課題 2 [30 点]
满足以下条件。
- N \leqq 100\,000.
- M \leqq 10.
小課題 3 [10 点]
满足以下条件。
- N \leqq 100\,000.
- M \leqq 500.
小課題 4 [25 点]
- M \leqq 5\,000 很满意。
小課題 5 [20 点]
没有其他限制。
入力例 1
5 3 1 2 3 3 2
出力例 1
2 1 1
使用以下操作 包含的成本 1 包括成本 2 中的长度 可以用 2 来匹配。
- 从左起 从第 2 为字符串着色 重新绘制为 1 ,长度从左算起 扭转,使 1 的位置成为终点。从左到右,绳子的颜色是 1, 3, 3, 2 厚度为 2, 1, 1, 1 变为。
- 从左起 从第 4 字符串的颜色 1 ,长度从左算起 扭转,使 2 的位置成为终点。从左到右,绳子的颜色是 3, 1 厚度为 2, 3 变为。
您还可以使用以下操作更改颜色。 2, 3 包括成本 1 中的长度 可以用 2 来匹配。
- 从左算起的长度 扭转,使 3 的位置成为终点。从左到右,绳子的颜色是 3, 2, 1 厚度为 2, 2, 1 变为。
- 从左起 从第 3 字符串的颜色 2 ,长度从左算起 扭转,使 2 的位置成为终点。从左到右,绳子的颜色是 2, 3 厚度为 3, 2 变为。
入力例 2
7 3 1 2 2 1 3 3 3
出力例 2
2 2 2
使用以下操作 包含的成本 1 包括成本 2 中的长度 可以用 2 来匹配。
- 从左算起的长度 扭转,使 2 位置成为终点。 扭转,使
- 从左起 从第 1 字符串的颜色 1 ,长度从左算起 扭转,使 1 的位置为终点。要重新绘制的字符串的粗细 2 因此,成本为 2 请注意,这将会发生。
- 从左算起的长度 扭转,使 3 位置成为终点。 扭转,使
- 从左算起的长度 扭转,使 1 位置成为终点。 扭转,使
入力例 3
10 3 2 2 1 1 3 3 2 1 1 2
出力例 3
3 3 4
1 在扭转之前,您可以在多个点重新绘制绳子。