Последовательность чисел монотонно убывающая если для любого i элемента (кроме последнего )выполняется Ai > Ai+1. Последовательность чисел монотонно возрастающая если для любого i элемента (кроме последнего )выполняется Ai < Ai+1. Последовательность монотонная если она или монотонно убывающая или монотонно возрастающая. Дана последовательность Ai из n чисел. Каждый элемент последовательности можно увеличивать или уменьшать. Требуется изменить последовательность так что бы в ней содержалось K монотонных непересекающихся последовательностей. (один элемент тоже последовательность). Т.к. преобразований бесконечно много то нужно найти такое преобразование чтобы сумма разностей по модулю конечного значения Ai и начального значения Ai была минимальна.
Входные данные
В первой строчке n,k n- количество элементов в последовательности, k сколько должно быть монотонных последовательностей. Во второй строчке n чисел через пробел - сама последовательность(каждое число по модулю меньше 20,000,000)
Выходные данные
Одно число, ответ на задачу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 1 1 1
|
1
|
|
2
|
6 1
1 2 3 3 2 1
|
9
|