Воздушные потоки

Колобок ушёл от бабушки и поехал путешествовать. Неожиданно для себя он забрёл в страну Ивэнлэнд. Первые трудности встали на его пути: Колобка и вход в страну отделял огромный ров с водой, которая, как известно, не очень хорошо влияет на нашего героя. К счастью, повсюду расположены воздушные потоки, которые могли поднимать того, кто на них встает, на определённую высоту. Страна не просто так названа Ивэнлэнд, поэтому все высоты, на которые могут поднять героя воздушные потоки --- это чётные числа.

Представим воздушные потоки как массив $h[1..n]$ из $n$ натуральных чисел --- высот потоков. Для каждого $1 \le i \le n$ посчитаем $G[i]$ --- индекс ближайшего элемента слева, строго большего $h[i]$. Более формально, $g[i] = \max\{j \,|\, j < i \mbox{ и } h[j] > h[i]\}$. Если $i = 1$ или до $h[i]$ нет ни одного элемента больше него, то $G[i]$ считается равным $0$.

Колобок считает, что оптимальность расположения воздушных потоков определяется суммой $$S(h) = \sum_{i=1}^n(i-G[i]).$$ Чем меньше сумма, тем расположение оптимальнее. Всё, что может сейчас сделать Колобок --- это увеличить высоту одного из воздушных потоков не более чем на $m$. После этого действия высота потока должна остаться целым числом, но может, если необходимо, стать и нечётной.

Помогите Колобку сделать оптимальное изменение, которое позволит добиться, чтобы сумма $S(h)$, описанная выше, после проделанного действия была минимальна.

В первой строке входного файла даны числа $n$, $m$ ($1 \le n \le 10^5$, $1 \le m \le 10^9$) --- количество воздушных потоков и максимальное значение, на которое можно увеличить высоту одного из них.

Во второй строке даны высоты воздушных потоков $h[i]$ ($1 \le h[i] \le 10^9$). Гарантируется, что все высоты --- чётные числа.

В единственной строке выходного файла выведите одно целое число --- минимальную искомую сумму.

В первом примере Колобку выгодно, например, увеличить первый элемент массива на 3, сделав его равным 7.

Тогда $h=[7, 2, 6]$, $G[1] = 0$, $G[2] = 1$ и $G[3] = 1$, сумма $S(h) = (1 - 0) + (2 - 1) + (3 - 1) = 1 + 1 + 2 = 4$. Добиться значения $S(h) < 4$ невозможно.

Во втором примере $m = 2$ и увеличить первый элемент так сильно не получится. После любого действия Колобка $S(h)$ будет равно 5 или 6, пример действия, которое приводит к значению 5 --- увеличить первый элемент на 1, получив массив $[5, 2, 6]$.