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$ минут.

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

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