ホットスポットとは、一般的に人々が無線ローカルエリアネットワーク（WLAN）を通じてインターネットにアクセスできる物理的な場所であり、ルーターがインターネットサービスプロバイダーに接続されています。多くの人はこれらの場所を「Wi-Fiホットスポット」と呼んでいます。公共のホットスポットは、通常、無線アクセスポイント（略してAP）によって作成されます。具体的には、ホットスポットとはAPが設置された場所から距離 $r$ 以内の領域のことです。言い換えれば、それはAPの場所を中心とする半径 $r$ の円です。

都市には長い直線道路があります。APはすでに道路沿いに設置されています。市の職員はホットスポットの半径を設定する必要があります。その際、任意の2つの異なるAPについて、それらから作成されるホットスポットは重なってはなりませんが、境界で接することは可能です。特別なケースとして、あるホットスポットの半径が0であり、別のホットスポットがその内部を含んでいる場合、その2つのホットスポットは重なっていると見なされ、これは許されません。しかし、半径が0であっても、そのホットスポットが別のホットスポットの境界に接することは可能です。

市の職員は、合計のカバー範囲が可能な限り広くなるようにホットスポットの半径を設定しようとしています。したがって、彼らはホットスポットの面積の合計、単純にはホットスポットの半径の二乗の合計を最大化しなければなりません。この目標を達成するために、いくつかのホットスポットの半径は0に設定される場合があります。

道路は平面上の直線と見なされ、道路上に設置されたAPの位置はその直線上の点となります。直線上の $n$ 個の点が与えられたとき、重なり合わないホットスポットの半径を決定し、それらの半径の二乗の合計が最大となるようにするプログラムを作成してください。

例えば、上の図のように、0、2、5の位置に3つのAPがあるとします。候補として、青と赤のホットスポットが与えられています。左から順に、青いホットスポットの半径は1、1、2です。このとき、半径の二乗の合計は6となります。しかし、赤いホットスポットの場合、半径は左から順に2、0、3です。したがって、半径の二乗の合計は13となり、これが最大値です。

入力

入力の最初の行には、APの数 $n$ ($2 \le n \le 3 \cdot 10^5$) が含まれます。2行目には、直線上のAPの位置を表す、$n$ 個の異なる整数が昇順でスペース区切りで並んでいます。ここで、整数は $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