Polycarp is practicing his problem solving skill. He has a list of $$$n$$$ problems with difficulties $$$a_1, a_2, \dots, a_n$$$, respectively. His plan is to practice for exactly $$$k$$$ days.每天他必须至少解决清单中的一个问题。 Polycarp solves the problems in the order they are given in his list, he cannot skip any problem from his list. He has to solve all $$$n$$$ problems in exactly $$$k$$$ days.
Thus, each day Polycarp solves a contiguous sequence of (consecutive) problems from the start of the list.他不能跳过问题或多次解决问题。 As a result, in $$$k$$$ days he will solve all the $$$n$$$ problems.
Polycarp练习第$$$j$$$日的利润是Polycarp在第$$$j$$$日解决的所有难题中最大的(即如果他在一天内解决了索引从$$$l$$$到$$$r$$$的问题,那么当天的利润为$$$\max\limits_{l \le i \le r}a_i$$$).他的执业总利润是他所有 $$$k$$$ 执业日利润的总和。
You want to help Polycarp to get the maximum possible total profit over all valid ways to solve problems.您的任务是在满足上述条件的 $$$k$$$ 天之间分配所有 $$$n$$$ 问题,以使总利润最大。
例如,如果 $$$n = 8、k = 3$$$ 且 $$$a = [5, 4, 2, 6, 5, 1, 9, 2]$$$,则总利润最大的可能分布之一为:$$$[5, 4, 2], [6, 5], [1, 9, 2]$$$。 Here the total profit equals $$$5 + 6 + 9 = 20$$$.
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2000$$$) — 分别是问题数和天数。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2000$$$) — Polycarp 列表中问题的难度,按照它们在列表中的放置顺序(即按照 Polycarp 将解决它们的顺序)。
输出
在输出的第一行打印最大可能的总利润。
在第二行中准确打印 $$$k$$$ 正整数 $$$t_1, t_2, \dots, t_k$$$ ($$$t_1 + t_2 + \dots + t_k$$$ 必须等于 $$$n$$$),其中 $$$t_j$$$ 表示 Polycarp 在第 $$$j$$$ 天将解决的问题数量以实现他的实践的最大可能的总利润。
如果有很多可能的答案,您可以打印其中任何一个。
示例
输入 #1
8 3 5 4 2 6 5 1 9 2
输出 #1
20 3 2 3
输入 #2
5 1 1 1 1 1 1
输出 #2
1 5
输入 #3
4 2 1 2000 2000 2
输出 #3
4000 2 2
注意
第一个示例在问题陈述中进行了描述。
在第二个示例中,只有一种可能的分布。
在第三个示例中,最佳答案是按以下方式分配问题:$$$[1, 2000], [2000, 2]$$$。此次分配的总利润为$$$2000 + 2000 = 4000$$$。