Hotspot to fizyczna lokalizacja, w której ludzie mogą korzystać z Wi-Fi, aby uzyskać dostęp do Internetu za pośrednictwem bezprzewodowej sieci lokalnej (WLAN) z routerem podłączonym do dostawcy usług internetowych. Większość ludzi nazywa te miejsca „hotspotami Wi-Fi”. Publiczne hotspoty są zazwyczaj tworzone przez bezprzewodowe punkty dostępowe, w skrócie AP (ang. access points). Konkretnie, hotspot to strefa w odległości $r$ od miejsca zainstalowania punktu dostępowego. Innymi słowy, jest to koło o promieniu $r$ ze środkiem w lokalizacji punktu dostępowego.

W mieście znajduje się długa, prosta droga. Punkty dostępowe są już zainstalowane wzdłuż drogi. Władze miasta muszą ustalić promienie hotspotów. Dla każdych dwóch różnych punktów dostępowych, utworzone przez nie hotspoty nie powinny się nakładać, ale mogą stykać się swoimi brzegami. Jako przypadek szczególny, jeśli promień hotspotu wynosi zero, a inny hotspot zawiera go wewnątrz, to te dwa hotspoty nakładają się, co nie powinno mieć miejsca. Jednak nawet jeśli promień hotspotu wynosi zero, hotspot może dotykać granicy innego hotspotu.

Władze miasta starają się ustawić promienie hotspotów tak, aby ich całkowity obszar pokrycia był jak największy. W związku z tym mają zmaksymalizować sumę pól powierzchni hotspotów, czyli po prostu sumę kwadratów promieni hotspotów. Aby osiągnąć ten cel, niektóre promienie hotspotów mogą zostać ustawione na zero.

Droga jest traktowana jako linia na płaszczyźnie, a lokalizacje punktów dostępowych zainstalowanych na drodze są punktami na tej linii. Napisz program, który dla danych $n$ punktów na linii wyznaczy promienie niezachodzących na siebie hotspotów tak, aby suma kwadratów tych promieni była możliwie największa.

Na przykład, na powyższym rysunku znajdują się trzy punkty dostępowe zlokalizowane odpowiednio w 0, 2 i 5. Jako kandydatów podano niebieskie i czerwone hotspoty. Promienie niebieskich hotspotów wynoszą odpowiednio 1, 1 i 2, patrząc od lewej do prawej. Wtedy suma kwadratów promieni wynosi 6. Jednak dla czerwonych hotspotów ich promienie wynoszą 2, 0 i 3, patrząc od lewej do prawej. Zatem suma kwadratów promieni wynosi 13, co jest wartością maksymalną.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą $n$, liczbę punktów dostępowych ($2 \le n \le 3 \cdot 10^5$). Druga linia zawiera $n$ różnych liczb całkowitych oddzielonych spacjami, podanych w ściśle rosnącej kolejności, reprezentujących lokalizacje punktów dostępowych na linii, gdzie liczby całkowite mieszczą się w przedziale od 0 do $10^9$ włącznie.

Wyjście

Wypisz jedną liczbę całkowitą: maksymalną sumę kwadratów promieni hotspotów.

Przykład

Wejście 1

3
0 2 5

Wyjście 1

13

Wejście 2

4
0 1 3 6

Wyjście 2

10

Wejście 3

5
5 7 12 13 15

Wyjście 3

9