Un point d'accès (hotspot) est un lieu physique où les gens peuvent généralement utiliser le Wi-Fi pour accéder à Internet via un réseau local sans fil (WLAN) avec un routeur connecté à un fournisseur d'accès à Internet. La plupart des gens appellent ces endroits des « points d'accès Wi-Fi ». Les points d'accès publics sont généralement créés à partir de points d'accès sans fil, appelés en abrégé AP. Plus précisément, un point d'accès est une zone située à une distance $r$ de l'endroit où un AP est installé. En d'autres termes, il s'agit d'un cercle de rayon $r$ centré à l'emplacement de l'AP.

Dans une ville, il y a une longue route droite. Les AP sont déjà installés le long de la route. Les responsables de la ville doivent définir les rayons des points d'accès. Ensuite, pour deux AP différents, les points d'accès créés à partir de ceux-ci ne doivent pas se chevaucher, mais ils peuvent se toucher à leurs frontières. Dans un cas particulier, si le rayon d'un point d'accès est nul et qu'un autre point d'accès le contient, alors les deux points d'accès se chevauchent, ce qui ne devrait pas arriver. Mais même si le rayon d'un point d'accès est nul, le point d'accès peut toucher la frontière d'un autre point d'accès.

Les responsables de la ville essaient de définir les rayons des points d'accès de telle sorte que leur zone de couverture totale soit aussi grande que possible. Ainsi, ils doivent maximiser la somme des aires des points d'accès, simplement la somme des carrés des rayons des points d'accès. Pour atteindre cet objectif, certains rayons de points d'accès peuvent être fixés à zéro.

La route est considérée comme une ligne sur le plan, et les emplacements des AP installés sur la route sont des points sur la ligne. Écrivez un programme qui, étant donné $n$ points sur la ligne, déterminera les rayons des points d'accès sans chevauchement de telle sorte que la somme des carrés de ces rayons soit la plus grande possible.

Par exemple, il y a trois AP situés respectivement à 0, 2 et 5, dans la figure ci-dessus. À titre de candidat, les points d'accès bleus et rouges sont donnés. Les rayons des points d'accès bleus sont 1, 1 et 2, de gauche à droite. Alors la somme des carrés des rayons est 6. Mais pour les points d'accès rouges, leurs rayons sont 2, 0 et 3, de gauche à droite. Ainsi, la somme des carrés des rayons est 13, ce qui est le maximum.

Entrée

La première ligne de l'entrée contient un entier $n$, le nombre d'AP ($2 \le n \le 3 \cdot 10^5$). La deuxième ligne contient $n$ entiers distincts séparés par des espaces dans un ordre strictement croissant représentant les emplacements des AP sur la ligne, où les entiers sont compris entre 0 et $10^9$ inclus.

Sortie

Affichez un entier : la somme maximale des carrés des rayons des points d'accès.

Exemples

Entrée 1

3
0 2 5

Sortie 1

13

Entrée 2

4
0 1 3 6

Sortie 2

10

Entrée 3

5
5 7 12 13 15

Sortie 3

9