删除子数组

题目描述

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

你可以进行任意次(可能为 $0$ 次)以下操作。

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

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

求使数组 $A$ 的元素和等于 $x$ 所需的最少操作次数。 如果无法使数组 $A$ 的元素和等于 $x$,则输出 -1。

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

输入格式

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

$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

数据范围

• $1 \le N,M \le 3000$
• $1 \le a_i \le 3000$
• 输入中的所有值均为整数。