Hotspots

A hotspot is a physical location where people can generally use Wi-Fi to access the Internet through a wireless local-area network (WLAN) with a router connected to an Internet service provider. Most people call these places "Wi-Fi hotspots". Public hotspots are typically created from wireless access points, or APs. Specifically, a hotspot is a zone within distance $r$ of the AP where it is installed. That is, it is a circle with radius $r$ centered at the AP's location.

A city has a long straight road, and APs are already installed along it. The city officials need to set the radii of the hotspots. For any two different APs, their hotspots must not overlap, but they may touch at their boundaries. As a special case, if a hotspot with radius 0 lies inside another hotspot, the two overlap, which is not allowed. A hotspot with radius 0 may still touch the boundary of another hotspot.

The officials want the coverage areas to be as large as possible. So they maximize the sum of the areas of the hotspots, that is, the sum of the squares of the radii. Some radii may be set to 0 to achieve this.

The road is a line on the plane, and the AP locations are points on that line. Given $n$ points on the line, find the radii that maximize the sum of the squares of the radii while the hotspots do not overlap.

For example, suppose three APs are located at 0, 2, and 5, as in the figure below.

The blue hotspots have radii 1, 1, and 2 from left to right, so the sum of the squares is 6. The red hotspots have radii 2, 0, and 3 from left to right, so the sum is 13, which is the maximum.

The first line contains an integer $n$ ($2 \le n \le 3,000$), the number of APs. The second line contains $n$ distinct integers separated by spaces, in increasing order, giving the AP locations. Each integer is between 0 and $10^9$.

Print one line containing a nonnegative integer, the maximum sum of the squares of the hotspot radii.