Задача: Перекошенное разбиение

Дан массив \([a_1, a_2, \ldots, a_n]\), состоящий из неотрицательных целых чисел.

Рассмотрим разбиение массива на \(k\) непустых отрезков подряд идущих элементов. Назовем перекосом разбиения разность между максимальной и минимальной суммой чисел в отрезках разбиения. Требуется найти максимальный перекос разбиения данного массива на \(k\) подотрезков.

Например, если массив равен \([2, 1, 3, 4]\), то у разбиения \([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 300\,000\)) — длину массива и количество подотрезков, соответственно.

Вторая строка содержит \(n\) целых чисел \(a_i\) (\(0 \le a_i \le 10^9\)) — элементы массива.

Формат выходных данных
Выведите одно число — максимальный перекос разбиения данного массива на \(k\) отрезков.

Примечание
Первый пример разобран в условии задачи.

Во втором примере оптимальным разбиением является \([2][1][3, 4][1]\). Максимальная сумма на подотрезках в данном разбиении равна \(3 + 4 = 7\), минимальная сумма равна \(1\), таким образом, перекос равен \(6\).

Ваш ответ: