Наименьший общий предок


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 24765. Воздушные потоки
Темы: Деревья    Наименьший общий предок    Разреженные таблицы (sparse table)    Структуры данных    Префиксные суммы(минимумы, ...)   

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

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

Колобок считает, что оптимальность расположения воздушных потоков определяется суммой


Чем меньше сумма, тем расположение оптимальнее. Всё, что может сейчас сделать Колобок — это увеличить высоту одного из воздушных потоков не более чем на m. После этого действия высота потока должна остаться целым числом, но может, если необходимо, стать и нечётной.

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

Формат входного файла
В первой строке входного файла даны числа n, m (1 ≤ n ≤ 105 , 1 ≤ m ≤ 109 ) — количество воздушных потоков и максимальное значение, на которое можно увеличить высоту одного из них. Во второй строке даны высоты воздушных потоков h[i] (1 ≤ h[i] ≤ 109 ). Гарантируется, что все высоты — чётные числа.

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

Ввод Вывод
3 100
4 2 6
4
3 2
4 2 6
5
3 10
2 2 2
4