熱點（hotspot）是一個物理位置，人們通常可以透過連接到網際網路服務供應商路由器的無線區域網路（WLAN）來使用 Wi-Fi 上網。大多數人稱這些地方為「Wi-Fi 熱點」。公共熱點通常由無線存取點（Wireless Access Points，簡稱 AP）建立。具體來說，熱點是一個距離 AP 安裝位置 $r$ 以內的區域。換句話說，它是一個以 AP 位置為圓心、半徑為 $r$ 的圓。

在城市中，有一條筆直的長路。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

輸出

13

範例 2

輸入

4
0 1 3 6

輸出

10

範例 3

輸入

5
5 7 12 13 15

輸出

9