Гірська траса#7489
У передмісті Алмати створено туристичний гірський круговий маршрут, де старт і фініш збігаються в одній точці. Цей маршрут можна уявити як сходинок однакової ширини, де кожна -та сходинка має висоту над рівнем моря a_i у метрах. Сусідні сходинки можуть бути на одній висоті. Складність маршруту визначається сумарною величиною спусків і підйомів, що обчислюється за формулою:
З'ясувалося, що початковий маршрут виявився занадто складним для туристів. Щоб його спростити, можна використати блоків. Кожен блок має таку ж ширину, як і сходинка, а його висота становить метр. Будь-який блок можна поставити на будь-яку сходинку або на вже поставлений блок, або не використовувати взагалі.
Яке максимальне зменшення складності маршруту можна отримати?
Перший рядок містить числа (2 \le n \le 10^6) і (1 \le k \le 10^9). У наступному рядку наведено цілих невід'ємних чисел, що представляють висоти кожної зі сходинок.
Виведіть одне число — максимально можливе зменшення складності маршруту.
Приклад 1
Приклад 2
Приклад 3