Волшебная шахта
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Волшебники-шахтеры занимаются изучением наличия полезных магических ископаемых. Сейчас им поручено выкопать как можно более глубокую шахту, чтобы проверить наличие магических ископаемых в регионе. Ландшафт региона может быть представлен как последовательность столбов земли, $$$i$$$-й из которых имеет высоту $$$h_i$$$ метров, и бесконечен в глубину. Шахтеры могут за одну минуту удалить $$$1$$$ метр земли сверху любого столба. Чтобы не произошло обрушение во время раскопок, требуется, чтобы после каждой операции разница высот любых двух соседних столбов не превосходила $$$1$$$. Изначальный ландшафт также удовлетворяет этим ограничениям.

Помогите шахтерам определить минимальную глубину, которую они могут достигнуть за $$$t$$$ минут.

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

В первой строке даны два целых числа $$$n$$$ и $$$t$$$ — количество столбов земли и время, которое шахтеры будут копать ($$$1 \le n \le 100\,000$$$, $$$1 \le t \le 10^{18}$$$). В следующей строке даны $$$n$$$ целых чисел $$$h_i$$$ — исходные высоты столбов земли ($$$1 \le h_i \le 10 ^ 9$$$). Гарантируется, что $$$|h_i - h_{i + 1}| \le 1$$$ для всех $$$i \in [1 \dots n - 1]$$$.

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

В единственной строке выведите одно целое число — минимальную глубину, которую шахтеры могут достигнуть за $$$t$$$ минут.

Примеры

Входные данные
5 2
3 2 2 3 4
Выходные данные
1
Входные данные
5 10
3 2 2 3 4
Выходные данные
-1

Примечание

Пояснение к первому тесту, штрихованным отмечены части, которые нужно выкопать:

Пояснение ко второму тесту: