AT_abc275_f.[ABC275F] Erase Subarrays

给定一个正整数序列 $A=(a_1,a_2,\ldots,a_N)$。
你可以重复进行如下操作任意次（包括 $0$ 次）：

• 从 $A$ 中选择一个（非空的）连续子序列并将其删除。

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

• 求将 $A$ 的元素总和恰好变为 $x$ 所需的最小操作次数。如果无论如何操作都无法使 $A$ 的元素总和恰好变为 $x$，则输出 $-1$。

另外，当 $A$ 为空时，$A$ 的元素总和视为 $0$。

输入以如下格式从标准输入给出。

$N$ $M$ $a_1$ $\ldots$ $a_N$

输出 $M$ 行。第 $i$ 行输出对应 $x=i$ 的答案。

限制条件

• $1 \leq N, M \leq 3000$
• $1 \leq a_i \leq 3000$
• 输入均为整数

样例解释 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$。

由 ChatGPT 4.1 翻译