热点（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

样例输出 1

13

样例输入 2

4
0 1 3 6

样例输出 2

10

样例输入 3

5
5 7 12 13 15

样例输出 3

9