За связь без перебоев

Вдоль прямой дороги, на которой происходят испытания беспилотных грузовиков, расположены $n$ городов, $i$-й город находится в точке, имеющей координату $i$. В $i$-м городе установлена антенна мощностью $a_i$, покрывающая все города от $L_i = \max\left(1, i - a_i\right)$ до $R_i = \min(n, i + a_i)$ включительно.

Беспилотный грузовик перемещается вдоль дороги от города $s$ к городу $t$, где $s < t$. В каждом городе по пути следования грузовик подключён к одной из антенн. Подключение к антеннам происходит следующим образом.

• В начальном городе грузовик подключается к антенне, покрывающей этот город, у которой значение $R_i$ максимально. Если таких антенн несколько, выбирается любая из них.
• После перемещения грузовика из города $v$ в город $v+1$, если антенна, к которой он был подключен в городе $v$, покрывает также и город $v+1$, грузовик остаётся подключен к этой антенне. Иначе, если антенна, к которой он был подключён, не покрывает город $v+1$, грузовик переподключается к антенне, покрывающей город $v+1$, для которой значение $R_i$ максимально. Если таких антенн несколько, выбирается любая из них.

Обозначим как $f(s, t)$ количество переподключений между антеннами для грузовика, который начинает свой маршрут в городе $s$ и заканчивает свой маршрут в городе $t$ ($s < t$). Начальное подключение к антенне в городе $s$ переподключением не считается.

Нестойкостью покрытия дороги антеннами назовем сумму значений $f(s, t)$ по всем допустимым парам городов, то есть величину $$F= \sum\limits_{s=1}^{n-1} \sum\limits_{t=s+1}^{n} f(s, t). $$

В распоряжении оператора дороги есть одна запасная антенна с мощностью $x$. Для снижения нестойкости покрытия можно заменить одну из антенн на запасную. Требуется определить минимальное значение нестойкости покрытия дороги $F$, если не более одной антенны можно заменить на запасную антенну мощности $x$.

Первая строка содержит два целых числа $n$ и $x$ ($1 \le n \le 10^6$, $0 \le x \le n$) --- количество городов и мощность запасной антенны.

Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n$) --- мощности антенн.

Выведите минимальное возможное значение нестойкости покрытия дороги, если не более одной антенны можно заменить на запасную антенну мощности $x$.

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

Во втором примере использовать запасную антенну не нужно. Грузовикам, стартующим в одном из первых трёх городов и финиширующим в одном из двух последних городов придётся один раз переподключиться к последней антенне, поэтому нестойкость покрытия дороги равна 6.