핫스팟(hotspot)은 사람들이 무선 근거리 통신망(WLAN)을 통해 인터넷 서비스 제공업체에 연결된 라우터를 사용하여 인터넷에 접속할 수 있는 물리적 위치를 말합니다. 대부분의 사람들은 이러한 장소를 "Wi-Fi 핫스팟"이라고 부릅니다. 공공 핫스팟은 일반적으로 무선 액세스 포인트(AP)에 의해 생성됩니다. 구체적으로, 핫스팟은 AP가 설치된 곳으로부터 거리 $r$ 이내의 영역입니다. 즉, AP의 위치를 중심으로 하는 반지름 $r$의 원입니다.

도시에는 길고 곧은 도로가 있습니다. 도로를 따라 AP들이 이미 설치되어 있습니다. 시 관계자는 핫스팟의 반지름을 설정해야 합니다. 이때, 서로 다른 두 AP에서 생성된 핫스팟은 서로 겹치지 않아야 하지만, 경계에서 만나는 것은 가능합니다. 특별한 경우로, 어떤 핫스팟의 반지름이 0이고 다른 핫스팟이 그 핫스팟을 내부에 포함한다면 두 핫스팟은 겹치는 것으로 간주하며, 이는 허용되지 않습니다. 하지만 핫스팟의 반지름이 0이라 하더라도 다른 핫스팟의 경계에 닿는 것은 가능합니다.

시 관계자는 핫스팟의 총 커버리지 영역이 최대한 넓어지도록 반지름을 설정하고자 합니다. 따라서 그들은 핫스팟 영역의 합, 즉 단순히 핫스팟 반지름의 제곱의 합을 최대화해야 합니다. 이 목표를 달성하기 위해 일부 핫스팟의 반지름은 0으로 설정될 수 있습니다.

도로는 평면 위의 직선으로 간주하며, 도로에 설치된 AP들의 위치는 직선 위의 점들입니다. 직선 위에 주어진 $n$개의 점에 대해, 겹치지 않는 핫스팟들의 반지름을 결정하여 그 반지름 제곱의 합이 최대가 되도록 하는 프로그램을 작성하십시오.

예를 들어, 위 그림과 같이 0, 2, 5 위치에 세 개의 AP가 있다고 가정해 봅시다. 후보로 파란색 핫스팟과 빨간색 핫스팟이 주어집니다. 왼쪽부터 순서대로 파란색 핫스팟의 반지름은 1, 1, 2입니다. 이때 반지름 제곱의 합은 6입니다. 하지만 빨간색 핫스팟의 경우, 왼쪽부터 순서대로 반지름이 2, 0, 3입니다. 따라서 반지름 제곱의 합은 13이며, 이것이 최댓값입니다.

입력

첫 번째 줄에는 AP의 개수 $n$ ($2 \le n \le 3 \cdot 10^5$)이 주어집니다. 두 번째 줄에는 직선 위에 있는 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