Карс возмущен узким мышлением жителей своей деревни, поскольку они довольствуются тем, что стоят на месте, и не пытаются стать совершенной формой жизни. Будучи первоклассным изобретателем, Карс хочет усовершенствовать свое тело и стать совершенной формой жизни. К сожалению, \(n\) жителей деревни с подозрением относятся к его идеям. \(i\)-й житель деревни подозревает Карса на \(a_i\). По отдельности каждый житель деревни боится Карса, поэтому они объединяются в группы, чтобы стать сильнее.
Силу группы сельчан от \(l\) до \(r\) можно определить как \(f(l,r)\), где \(\)f(l,r) = |a_l - a_{l+1}| + |a_{l + 1} - a_{l + 2}| + \ldots + |a_{r-1} - a_r|.\(\) Здесь \(|x-y|\) — модуль числа \(x-y\). Группа с одним жителем имеет силу \(0\).
Карс хочет разбить жителей деревни на ровно \(k\) подряд идущих групп так, чтобы сумма их сил была минимальна. Формально, он должен найти \(k - 1\) положительных целых чисел \(1 \le r_1 < r_2 < \ldots < r_{k - 1} < n\) такие, что \(f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)\) минимально. Помогите Карсу найти минимальное значение \(f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимально возможное значение суммы сил всех групп, т. е. минимально возможное значение \(f(1,r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)\).
Примечание
В первом наборе входных данных сгруппируем жителей деревни с подозрениями \((1,3,5,2)\) в \((1,3,5)\) и \((2)\). Таким образом, \(f(1,3) + f(4,4) = (|1 - 3| + |3 - 5|) + 0 = 4 + 0 = 4\).
Во втором наборе входных данных мы сгруппируем жителей деревни с подозрениями \((1,9,12,4,7,2)\) в \((1),(9,12),(4,7,2)\). Итак, \(f(1,1) + f(2,3) + f(4,6) = 0 + 3 + 8 = 11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 2
1 3 5 2
6 3
1 9 12 4 7 2
12 8
1 9 8 2 3 3 1 8 7 7 9 2
|
4
11
2
|