感觉其他题解证明的相对有点繁琐 w，我来证一个。

我们声称传消息的人是 Alice，接收消息的人是 Bob。

考虑 Alice 的策略。

我们考虑钦定一个 $V \ge \max_{i=1}^{n} a_i$，然后贪心分成若干个和 $\le V$ 的段（即能不断就不断），找到最小的 $V$ 使得贪心划分的段数 $\le K$，此时加 $K - 1$ 个数可以使得每一段的和均相等（加的数不要求在段内仍然呈现升序关系），考虑证明：

先特判掉 $V = \max_{i=1}^{n} a_i$ 最优的情况，即此时划分段数 $\le K$，我们给每一段加上 $S_i - V$ 即可，$S_i$ 表示第 $i$ 段的和，因为存在 $a_i = V$，因此必定有一段不需要加数，只需要添加 $\le K - 1$ 个数字。

特判完这个后也就是说明存在一个 $V$ 使得存在合法划分并且划分段数 $> K$ 了，那么我们考虑证明此时必然存在一个 $V$ 满足划分段数 $= K$。

具体地，考虑一个划分段数 $< K$ 的方案的 $V$，若我们将 $V \gets V - 1$，那么容易证明每一段至多减少一个数，增加一个数，由于原来的 $V$ 的划分方案有一段是空的，因此现在的 $V$ 最坏情况下也就只会存在一个数字，那么总和是一定 $\le M$ 的，不高于 $V$ 的下界，因此划分段数一定不会 $> K$，这样调整后仍然是合法的。

继续观察，你发现当 $V \gets V - 1$ 后，$K$ 至多变大 $1$，且存在一个划分段数 $> K$ 的划分方案，因此划分段数 $= K$ 的方案是一定存在的。

那么此时存在划分段数 $=K$ 的方案，如何保证加的数字不超过 $K - 1$ 呢？这部分比较简单，只需要令 $V = \max_{i=1}^{K} S_i$ 即可，在实现时你也可以直接二分最小的满足条件（划分段数 $\le K$）的 $V$，这个 $V$ 其实天然满足（除去一开始特判掉的情况）划分段数 $= K$，且有 $V = \max_{i=1}^{K} S_i$，这部分比较容易理解，不多赘述。

到这里，Alice 的策略就比较清晰了，只需要二分出最小的满足条件的 $V$ 后贪心划分即可。

接下来我们只需要考虑 Bob 的策略。

考虑维护 $K$ 个空集，从大往小加入数字，每次将数字加到编号最小的能加入的集合内即可完成构造，考虑证明：

考虑每一段的加入的数字一定 $<$ 下一段除去加入数字的最小数字，否则下一段的最小数字会被划分到此段中。

考虑最后一段，一定是一个后缀加上加入的一个数字（或不加入数字），由于是从大到小加入数字，因此和最终必定为 $V$。之后的段同理，仍然是此时的后缀加上一个数的形式，因此最终所有集合的数字和一定全部相等。

至此我们构造了一个集合划分方案，完成了 Bob 的策略。

由于集合和按照编号大小有单调性，于是可以直接通过线段树二分进行维护，至此我们完成了这个题。