Split the sequence

Time limit2sMemory limit128 MB

Summary

Split the sequence into k+1 contiguous parts so the total product score from the cuts is maximal, and print the score with one optimal cut list.

Level: Medium7 of 10
Topics: Dynamic programming, Divide and conquer, Math, Prefix sum
Solved: No attempts yet

Problem

Split a sequence of $n$ nonnegative integers into $k+1$ nonempty contiguous parts using $k$ cuts. Each cut splits one current part into two, and the score gained is the product of the sums of the two new parts. The order of cuts does not change the total score. Find the maximum total score and one valid list of cut positions.

Input

The first line contains $n$ and $k$ ( $2 \le n \le 100000$ , $1 \le k \le \min(n-1, 200)$ ). The second line contains $a_1, \ldots, a_n$ ( $0 \le a_i \le 10^4$ ).

Output

Print the maximum score on the first line. On the second line print $k$ cut positions in order. Any optimal answer is accepted.

Examples1

Example 1
Input
```
7 3
4 1 3 4 0 2 3
```
Expected output
```
108
1 3 5
```