Горная трасса
В окрестностях Алматы оборудован туристический горный круговой маршрут (старт и финиш находятся в одной точке). Будем моделировать этот маршрут n ступеньками одинаковой ширины, задавая каждую i-ю ступеньку ее высотой над уровнем моря a[i] в метрах. Соседние ступеньки могут иметь одинаковую высоту. Сложность трассы определяется суммарным значением спусков и подъемов. Или формально,
difficulty = |a[1] - a[2]| + |a[2] - a[3]| + ... + |a[n-1] - a[n]| + |a[n] - a[1]|
Оказалось, что первоначально сконструированная трасса слишком сложна для туристов. Для того чтобы ее упростить, мы можем использовать k блоков. Ширина каждого блока совпадает с шириной ступеньки, а высота равна 1 метру. Любой из блоков можно положить на любую ступеньку или ранее положенный блок или не использовать совсем.
На сколько таким образом можно уменьшить сложность трассы в целом?
Входные данные
В первой строке находятся числа n (2 ≤ n ≤ 10^6) и k (1 ≤ k ≤ 10^9). В следующей строке находятся n целых неотрицательных чисел - высоты каждой из ступенек.
Выходные данные
Запишите одно число - максимально возможное уменьшение сложности трассы.