핫스팟

핫스팟은 사람들이 라우터를 거쳐 인터넷 서비스 제공자에 연결된 무선 랜(WLAN)을 통해 인터넷에 접속할 수 있는 실제 장소를 말한다. 많은 사람이 이를 '와이파이 핫스팟'이라고 부른다. 공용 핫스팟은 보통 무선 액세스 포인트(AP)로 만든다. 구체적으로, 핫스팟은 AP가 설치된 위치에서 거리 $r$ 이내에 있는 영역이다. 즉, AP 위치를 중심으로 하고 반지름이 $r$인 원이다.

한 도시에 긴 직선 도로가 있고, 그 도로를 따라 AP가 이미 설치되어 있다. 시 당국은 핫스팟의 반지름을 정해야 한다. 서로 다른 두 AP의 핫스팟은 겹치면 안 되지만, 경계에서 맞닿는 것은 허용된다. 특별한 경우로, 반지름이 0인 핫스팟이 다른 핫스팟 안에 들어가면 두 핫스팟이 겹치므로 허용되지 않는다. 반지름이 0인 핫스팟이라도 다른 핫스팟의 경계에 닿는 것은 괜찮다.

당국은 커버하는 면적을 최대한 넓히려고 한다. 따라서 핫스팟 면적의 합, 즉 반지름 제곱의 합을 최대화한다. 이를 위해 일부 반지름을 0으로 정할 수 있다.

도로는 평면 위의 직선이고, AP의 위치는 그 직선 위의 점이다. 직선 위에 주어진 $n$개의 점에 대해, 핫스팟이 서로 겹치지 않으면서 반지름 제곱의 합을 최대로 하는 반지름을 구하라.

예를 들어, 아래 그림과 같이 AP 세 개가 0, 2, 5 위치에 있다고 하자.

파란색 핫스팟의 반지름은 왼쪽부터 1, 1, 2이며, 반지름 제곱의 합은 6이다. 빨간색 핫스팟의 반지름은 왼쪽부터 2, 0, 3이며, 합은 13으로 최대이다.

첫째 줄에 AP의 개수를 나타내는 정수 $n$ ($2 \le n \le 3,000$)이 주어진다. 둘째 줄에는 AP의 위치를 나타내는 서로 다른 정수 $n$개가 공백으로 구분되어 오름차순으로 주어진다. 각 정수는 0 이상 $10^9$ 이하이다.

핫스팟 반지름 제곱의 합의 최댓값을 나타내는 음이 아닌 정수를 한 줄에 출력한다.