E. Банановый бизнес Олега
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, в Капилэнде растет очень много бананов. В один солнечный день, капибара Олег решил собрать $$$n$$$ бананов и продать их на рынке. К каждому банану Олег прицепил ценник, на котором написано, сколько стоит банан.

В начальный момент времени $$$i$$$-й банан стоит $$$c_i$$$ капикойнов. Как известно, капибара мыслит следующим образом: она смотрит на два соседних банана, берет абсолютную разность между ценами этих бананов, и чем больше это значение, тем больше вероятность, что она купит дорогой банан (ведь чем больше разница между стоимостями, тем более вкусным будет дорогой банан). Соседними являются $$$i$$$-й и $$$(i + 1)$$$-й, где $$$1 \le i \lt n$$$, то есть два банана являются соседними, если их номера отличаются не более чем на единицу.

Олег может делать следующую операцию: взять два соседних банана и поменять их ценники местами. Олегу стало интересно, какую максимальную разность между ценами двух соседних бананов он сможет получить, если он выполнит эту операцию ровно $$$k$$$ раз. Помогите ему справиться с этой непростой задачей!

Входные данные

В первой строке даются два целых числа $$$n$$$ и $$$k$$$ $$$(2 \le n \le 10^5$$$, $$$0 \le k \le 10^{18})$$$ — количество бананов, а также количество раз, сколько нужно поменять ценники соседних бананов.

Во второй строке дается $$$n$$$ целых чисел $$$c_i$$$ $$$(1 \le c_i \le 10^9)$$$, где $$$c_i$$$ — стоимость $$$i$$$-го банана.

Система оценки

Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи
00Тесты из условия—
17$$$k = 0$$$—
28$$$k = 1$$$—
35$$$k = 10^{18}$$$—
415$$$n \le 9$$$0
516$$$n \le 10^3$$$0, 4
619$$$k \le 100$$$1, 2
730—0-6
Примеры
Входные данные
4 0
1 3 2 4
Выходные данные
2
Входные данные
4 2
1 3 2 4
Выходные данные
3
Входные данные
4 10000
1 3 2 4
Выходные данные
3
Входные данные
8 3
10 4 2 12 10 4 22 23
Выходные данные
20
Примечание

Во втором примере $$$k = 2$$$. Первой операцией поменяем ценники третьего и четвертого банана. Ценники будут выглядеть после этого как $$$[1,\ 3,\ 4,\ 2]$$$. Второй операцией поменяем ценники второго и третьего банана. Ценники будут выглядеть после этого как $$$[1,\ 4,\ 3,\ 2]$$$. Давайте посчитаем максимальную разность между ценами двух соседних бананов:

  • Между первым и вторым бананом разность ценников равна $$$|1 - 4| = 3$$$;
  • Между вторым и третьим бананом разность ценников равна $$$|4 - 3| = 1$$$;
  • Между третьим и четвёртым разность ценников равна $$$|3 - 2| = 1$$$.

Итого максимальная разность в данном случае максимальная разность будет равна $$$3$$$.