题目背景

翻译自 ROIR 2025 D2T2。

题目描述

给定一个非负整数数组 $[a_1, a_2, \dots, a_n]$。考虑将该数组划分成 $k$ 个非空的连续子段。我们称划分方案的“不平衡度”为这些子段和中的最大值与最小值之差。你需要求出将该数组划分成 $k$ 个子段时的最大不平衡度。

例如，如果数组为 $[2, 1, 3, 4]$，$k=2$，则：

• 划分为 $[2, 1, 3][4]$ 时，不平衡度为 $6 - 4 = 2$；
• 划分为 $[2, 1][3, 4]$ 时，不平衡度为 $7 - 3 = 4$；
• 划分为 $[2][1, 3, 4]$ 时，不平衡度为 $8 - 2 = 6$。

其中最后一种情况的不平衡度最大。

输入格式

第一行输入两个整数 $n$ 和 $k$（$2 \le k \le n \le 300000$），分别表示数组的长度和需要划分的子段的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$0 \le a_i \le 10^9$）。

输出格式

输出一个整数，即将该数组划分为 $k$ 个子段时的最大不平衡度。

4 2
2 1 3 4

6

5 4
2 1 3 4 1

6

提示

在样例二中，最优划分方案是 $[2][1][3, 4][1]$。其中最大子段和为 $3 + 4 = 7$，最小子段和为 $1$，因此不平衡度为 $7 - 1 = 6$。

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。