小 X 在最后一周的问求 OT 上听到了改变枚举顺序来简化求和式的做法，于是在复习问求时，他出了一道题考了考他的复习搭子小 C 同学。
考虑一个长为 的整数序列 ，其中整数编号从 到 。
现要将该序列分为至多 个连续子段，按照子段开头的整数编号排序后，记第 个子段的起始编号为 ，结束编号为 。
定义这个划分方案的价值为：
。
其中 是划分的子段的数量。
小 X 想问的是，价值最大的划分方案的价值（即 ）是多少？
第一行两个正整数 ，含义如题。
接下来一行 个整数，表示序列 ，含义如题。
一行一个整数，表示答案。
7 3 9 22 5 -3 7 -40 509
1518
对于 的数据，。