Падающий шарик

Алексей разрабатывает новую аркадную игру «Падающий шарик». Есть башня из N этажей, расположенных друг под другом. Каждый этаж – это горизонтальная платформа шириной M клеток, пронумерованных слева направо числами от 1 до M. На каждом этаже проделано одно круглое отверстие («лунка») шириной 1 клетка. Сразу после того, как шарик впервые оказывается над первым этажом, все лунки начинают одновременно двигаться: сначала на одну клетку вправо каждую секунду; достигнув правой стены (M), лунка разворачивается и каждую секунду перемещается на одну клетку влево, пока не дойдёт до левой стены (1), затем разворачивается снова – и так бесконечно. Шарик впервые появляется над первым этажом именно над лункой.

Игрок управляет шариком:

1. Падение сквозь лунку занимает ровно 1 секунду. После этого шарик оказывается поверх следующего этажа точно под тем же номером клетки, где была лунка, и может сразу начинать двигаться или падать дальше.
2. Пока шарик не совпадает по координате с лункой следующего этажа, каждую секунду он может:
   • остаться в той же клетке,
   • сместиться на 1 клетку влево,
   • сместиться на 1 клетку вправо.

Любое такое действие также длится 1 секунду.

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

Входные данные

В первой строке входного файла INPUT.TXT находятся два натуральных числа N – количество этажей и M – ширина платформы (1 ≤ N ≤ 10⁶; 1 ≤ M ≤ 10⁴). Во второй строке даны N натуральных чисел a_i - исходная позиция лунки на i-м этаже (1≤ a_i ≤ M).

Лунки нумеруются сверху вниз: a₁ – верхний этаж, a_N – нижний.

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

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

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]