28827번 - Волшебная шахта 다국어

문제

Волшебники-шахтеры занимаются изучением наличия полезных магических ископаемых. Сейчас им поручено выкопать как можно более глубокую шахту, чтобы проверить наличие магических ископаемых в регионе. Ландшафт региона может быть представлен как последовательность столбов земли, $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$ минут.

제한

노트

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

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