Хот-спот — это физическое место, где люди могут пользоваться Wi-Fi для доступа в Интернет через беспроводную локальную сеть (WLAN) с помощью маршрутизатора, подключенного к интернет-провайдеру. Большинство людей называют такие места «Wi-Fi хот-спотами». Публичные хот-споты обычно создаются с помощью беспроводных точек доступа, сокращенно AP (от англ. access points). В частности, хот-спот — это зона в пределах расстояния $r$ от места установки AP. Иными словами, это круг радиуса $r$ с центром в точке расположения AP.

В городе есть длинная прямая дорога. Вдоль дороги уже установлены AP. Городским властям необходимо задать радиусы хот-спотов. При этом для любых двух различных AP созданные ими хот-споты не должны перекрываться, но они могут соприкасаться своими границами. В качестве особого случая: если радиус хот-спота равен нулю, и другой хот-спот содержит его внутри себя, то эти два хот-спота перекрываются, чего быть не должно. Однако даже если радиус хот-спота равен нулю, хот-спот может касаться границы другого хот-спота.

Городские власти пытаются задать радиусы хот-спотов так, чтобы их общая площадь покрытия была как можно больше. Таким образом, они должны максимизировать сумму площадей хот-спотов, что эквивалентно максимизации суммы квадратов радиусов хот-спотов. Для достижения этой цели некоторые радиусы хот-спотов могут быть установлены равными нулю.

Дорога рассматривается как прямая на плоскости, а места расположения AP, установленных вдоль дороги, — как точки на этой прямой. Напишите программу, которая по заданным $n$ точкам на прямой определит радиусы неперекрывающихся хот-спотов так, чтобы сумма квадратов этих радиусов была максимально возможной.

Например, на рисунке выше есть три AP, расположенные в точках 0, 2 и 5 соответственно. В качестве варианта предложены синие и красные хот-споты. Радиусы синих хот-спотов слева направо равны 1, 1 и 2. Тогда сумма квадратов радиусов равна 6. Но для красных хот-спотов радиусы равны 2, 0 и 3 слева направо. Таким образом, сумма квадратов радиусов равна 13, что является максимумом.

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

Первая строка входных данных содержит целое число $n$, количество AP ($2 \le n \le 3 \cdot 10^5$). Вторая строка содержит $n$ различных целых чисел, разделенных пробелами, в строго возрастающем порядке, представляющих координаты AP на прямой, где числа находятся в диапазоне от 0 до $10^9$ включительно.

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

Выведите одно целое число: максимально возможную сумму квадратов радиусов хот-спотов.

Примеры

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

3
0 2 5

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

13

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

4
0 1 3 6

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

10

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

5
5 7 12 13 15

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

9