Score : $500$ points

问题描述

你给定一个整数数组 $A=(a_1,a_2,\ldots,a_N)$。

你可以执行以下操作任意次数（可能为零次）：

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

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

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

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given an integer array $A=(a_1,a_2,\ldots,a_N)$.
You may perform the following operation any number of times (possibly zero).

• Choose a nonempty contiguous subarray of $A$, and delete it from the array.

For each $x=1,2,\ldots,M$, solve the following problem:

• Find the minimum possible number of operations to make the sum of elements of $A$ equal $x$. If it is impossible to make the sum of elements of $A$ equal $x$, print -1 instead.

Note that the sum of elements of an empty array is $0$.

Constraints

• $1 \leq N,M \leq 3000$
• $1 \leq a_i \leq 3000$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$a_1$ $\ldots$ $a_N$

Output

Print $M$ lines. The $i$-th line should contain the answer for $x=i$.

Sample Input 1

4 5
1 2 3 4

Sample Output 1

1
2
1
1
1

The followings are examples of minimum number of operations that achieve the goal.

• For $x=1$, delete $a_2,a_3,a_4$, and the sum of elements of $A$ becomes $x$.
• For $x=2$, delete $a_3,a_4$, then delete $a_1$, and the sum of elements of $A$ becomes $x$.
• For $x=3$, delete $a_3,a_4$, and the sum of elements of $A$ becomes $x$.
• For $x=4$, delete $a_1,a_2,a_3$, and the sum of elements of $A$ becomes $x$.
• For $x=5$, delete $a_2,a_3$, and the sum of elements of $A$ becomes $x$.

Sample Input 2

1 5
3

Sample Output 2

-1
-1
0
-1
-1

Sample Input 3

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

Sample Output 3

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

update @ 2024/3/10 11:35:38