当前没有测试数据。

F - 删除子数组

分数：500分

问题描述

给定一个整数数组 $A=(a_1,a_2,\ldots,a_N)$。
你可以执行以下操作任意次数（可能为零）。

• 选择数组 $A$ 中的一个非空连续子数组，并将其从数组中删除。

对于每个 $x=1,2,\ldots,M$，解决以下问题：

• 找到使数组 $A$ 元素和等于 $x$ 的最小操作次数。如果无法使数组 $A$ 的元素和等于 $x$，则输出 -1。

注意，空数组的元素和为 $0$。

约束

• $1 \leq N,M \leq 3000$
• $1 \leq a_i \leq 3000$
• 输入中的所有值都是整数。

输入

从标准输入中按以下格式给出：

$N$ $M$

$a_1$ $\ldots$ $a_N$

输出

输出 $M$ 行。第 $i$ 行应包含 $x=i$ 时的答案。

4 5
1 2 3 4

1
2
1
1
1

以下是实现目标的最小操作次数的示例。

• 对于 $x=1$，删除 $a_2,a_3,a_4$，数组 $A$ 的元素和变为 $x$。
• 对于 $x=2$，删除 $a_3,a_4$，然后删除 $a_1$，数组 $A$ 的元素和变为 $x$。
• 对于 $x=3$，删除 $a_3,a_4$，数组 $A$ 的元素和变为 $x$。
• 对于 $x=4$，删除 $a_1,a_2,a_3$，数组 $A$ 的元素和变为 $x$。
• 对于 $x=5$，删除 $a_2,a_3$，数组 $A$ 的元素和变为 $x$。

1 5
3

-1
-1
0
-1
-1

12 20
2 5 6 5 2 1 7 9 7 2 5 5

2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1