#abc275f. [abc275_f]Erase Subarrays
[abc275_f]Erase Subarrays
Problem Statement
You are given an integer array .
You may perform the following operation any number of times (possibly zero).
- Choose a nonempty contiguous subarray of , and delete it from the array.
For each , solve the following problem:
- Find the minimum possible number of operations to make the sum of elements of equal . If it is impossible to make the sum of elements of equal , print
-1
instead.
Note that the sum of elements of an empty array is .
Constraints
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
Output
Print lines. The -th line should contain the answer for .
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 , delete , and the sum of elements of becomes .
- For , delete , then delete , and the sum of elements of becomes .
- For , delete , and the sum of elements of becomes .
- For , delete , and the sum of elements of becomes .
- For , delete , and the sum of elements of becomes .
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