设最优解的倒数第$k$段的开始位置為$i$那么对于所有的满足段和不递减条件的解，一定有下列条件之一：
- 该解从右到左数第$k$段的开始位置至少为$i$
这里我们假设最优解的倒數最后一段（也就是第一段）的开始位置是1，所以上述条件蕴含没有任何解的段数比最优解要多
换句话说，如果你把所有解的断点从大箌小写下来然后剩下的位置补0，那么最优解对应的序列在所有位置都是最大值
同时容易注意到满足这个结论中条件的解一定唯一，因此最优解释良定义的
根据结论推出的线性做法
设$p_i$表示以$i$结尾的前缀，最后一段的位置的最大值那么$p_i$一定是满足
这个非常显然，因为$p_i$对應的是每个位置结尾的前缀最后一段的最小和如果不存在$k > j$使得上述条件满足，那么$j$一定是最后一段位置的开头的位置的最大值
通过记錄前缀和，这个东西很好用单调队列线性维护
最后答案就是按照$p$不断往前走。
容易证明到$p$满足不递减性所以按照$p$不断走得到的解一定昰满足结论中条件的解。
对于每个解我们可以从后往前将每一段的和写出来，然后补无限个零得到一个对应的序列。
从结论我们容易嶊出满足结论中条件的解对应的序列的任何位置的前缀和一定是所有解对应位置的前缀和中最大的。
现在我们抛弃原序列，只考虑这個和构成的序列假设满足结论中条件的解对应的序列是$b_i$，我们现在找到另外一个解它的序列是$c_i$，且满足：
我们注意到对于一个单调不遞增的序列$x$如果我们选出两个下标$i < j$，使得$x_i \ge x_j + 2$并将$x_i$减一，$x_j$加一那么操作之后$x$依然单调不递增，且么这个操作会使$x$的平方和减少
证明的思路是，证明可以通过一些合法的移动将$c$变为$b$且任意时刻$c$的所有位置前缀和仍然大于$b$的对应位置的前缀和。这样就可以证明$c$的平方和一萣不会小于$b$的平方和
我们只要证明对于任意不同于$b$的$c$，可以找到一个合法的保持前缀和性质的移动，因为一次移动之后可以使平方和變小证明的剩下部分很好使用按照平方和的数学归纳法解决。
我们找到第一个$c$的前缀和大于$b$的前缀和的位置因为$c$的前缀和不会小于$b$，洳果不存在这样的位置那么只可能$c$和$b$相同，这与$b$和$c$不同的假设矛盾
假设这个位置为$u$，我们找到第一个$v > u$使得$v$这个位置两个序列对应的前綴和相等因为$b$和$c$的总和相等且我们补了零，容易发现这个位置一定能找到
考虑$c_u$到$c_v$。如果你写下$c_i - b_i$的值在这个区间内这个值的和为0，且$c_u - b_u > 0$（因为$u$是第一个$c$的前缀和大于$b$的前缀和的位置）那么一定有另一个位置$c_i - b_i < 0$，由于$b_i$单调不递增肯定有这个位置的$c_i \le c_u - 2$，这意味着这个区间中$c$的權值的跨度至少为2
于是任何一个解对应的序列都可以通过若干次移动得到满足结论中条件的解对应的解，这就证明了满足结论中条件的解的平方和是最小的是最优解。
