F - Erase Subarrays Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

正整数列 A=(a_1,a_2,\ldots,a_N) が与えられます。
あなたは次の操作を 0 回以上何度でも繰り返せます。

  • A から（空でない）連続する部分列を選び、削除する。

x=1,2,\ldots,M に対し、次の問題を解いてください。

  • A の要素の総和をちょうど x にするために必要な操作回数の最小値を求めてください。ただし、どのように操作を行っても A の要素の総和をちょうど x にできない場合は代わりに -1 と出力してください。

なお、A が空である時、A の要素の総和は 0 であるとします。

制約

  • 1 \leq N,M \leq 3000
  • 1 \leq a_i \leq 3000
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 \ldots a_N

出力

M 行出力せよ。i 行目には x=i に対する答えを出力せよ。

入力例 1

4 5
1 2 3 4

出力例 1

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 になります。

入力例 2

1 5
3

出力例 2

-1
-1
0
-1
-1

入力例 3

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

出力例 3

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

Score : 500 points

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