Путешествие по странам мира
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Даша решила совершить путешествие. Перед этим она выбрала $$$N$$$ городов, которые она хотела бы увидеть и для каждого города $$$i$$$ определила его красоту $$$x_{i}$$$.

Посетить город можно двумя способами:

  1. Проездом, в таком случае Даша получает $$$(x_{k} - c)^2$$$ удовольствия от посещения данного города
  2. Заехав в него, тогда Даша получит $$$(x_{k} - x_{\mathtt{prev}})^2$$$ удовольствия.
Где $$$k$$$ - номер посещаемого города, $$$s$$$ - номер последнего города, в который Даша заехала, $$$c$$$ - коэффициент получения счастья.

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

Input

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

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

Output

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

Examples

Input
6 3
5 1 6 5 0 1
Output
82
Input
6 -1
4 4 1 1 5 9
Output
138