Путешествие миньонов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Миньоны много путешествовали в поисках того, кто сможет стать их новым лидеров, перед тем, как встретились с Грю. Наиолее перспективными были $$$n$$$ городов, $$$i$$$-й из которых, по их оценкам, обладает перспективностью $$$a_{i}$$$.

Разумеется, это не единственный критерий оценки городов. Миньонам также важно весело провести время. При этом посетить город $$$i$$$ можно двумя способами:

  1. либо проездом, в случае чего миньоны получают $$$(a_{i} - c)^2$$$ удовольствия от посещения данного города;
  2. либо заехав в город на день, и в таком случае миньоны получат $$$(a_{i} - a_{\mathtt{prev}})^2$$$ удовольствия от его посещения, где $$$\mathtt{prev}$$$ — номер последеного города, в котором миньоны находились в течение дня (не проездом).

При этом в случае, когда миньоны в первый раз за всю поездку заезжают на день в какой-то город (пусть это город $$$i$$$), стоит считать $$$a_\mathtt{prev}$$$ равным $$$a_i$$$, и в таком случае они не получают удовольствия от его посещения.

Миньоны хотят посетить все города последовательно, то есть строго в порядке от $$$1$$$ до $$$n$$$, при этом, конечно же, они хотят получить от этого максимальное удовольствие. Подскажите им, какой максимальное удовольствие от такого путешествия можно получить.

При этом в города номер $$$1$$$ и номер $$$n$$$ обязательно заехать на день! Таким образом, удовольствия от посещения первого города они не получат.

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

В первой строке ввода даны два целых числа $$$n$$$ и $$$c$$$ — количество городов, которые миньоны хотят посетить, и параметр из условия ($$$1 \le n \le 10^6$$$; $$$-10^6 \le c \le 10^6$$$).

Во второй строке перечислены целые числа $$$a_i$$$ — значения перспективноти городов ($$$-10^6 \le a_i \le 10^6$$$).

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

Выведите единственное целое число — максимальное удовольствие, которое миньоны могут получить, посещая города последовательно, начиная с города под номером $$$1$$$ и заехав на день и в город $$$1$$$, и в город $$$n$$$.

Система оценки

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

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
0примеры из условияполная
130$$$n \le 500$$$0первая ошибка
220$$$n \le 2000$$$0, 1первая ошибка
320$$$a_i \le a_{i+1}$$$ для всех $$$ilt; n$$$первая ошибка
430без дополнительных ограничений0 – 3первая ошибка

Примеры

Входные данные
6 3
5 1 6 5 0 1
Выходные данные
82
Входные данные
6 -1
4 4 1 1 5 9
Выходные данные
138