408080: GYM102979 H Hotspot-2

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, shortly, APs. Specifically, a hotspot is a zone within distance $$$r$$$ from where an AP is installed. In other words, it is a circle with radius $$$r$$$ centered at the location of AP.

In a city, there is a long straight road. The APs are already installed along the road. The city officials need to set the radii of hotspots. Then, for any two different APs, the hotspots created from them should not overlap, but at their boundaries, they can meet. As a special case, if the radius of a hotspot is zero, and another hotspot contains it inside, then the two hotspots overlap, and it should not happen. But even if the radius of hotspot is zero, the hotspot can touch a boundary of another hotspot.

The city officials are trying to set the radii of hotspots such that their total coverage area is as large as possible. Thus, they shall maximize the sum of areas of hotspots, simply, the sum of squares of radii of hotspots. To achieve the goal, some radii of hotspots may be set to zero.

The road is considered as a line on the plane, and the locations of APs installed on the road are points on the line. Write a program that, given $$$n$$$ points on the line, will determine the radii of non-overlapping hotspots such that the sum of squares of these radii is maximum possible.

For example, there are three APs located at $$$0$$$, $$$2$$$, and $$$5$$$, respectively, in the above figure. As a candidate, the blue and red hotspots are given. The radii of the blue hotspots are $$$1$$$, $$$1$$$, and $$$2$$$, from left to right. Then the sum of squares of radii is $$$6$$$. But for the red hotspots, their radii are $$$2$$$, $$$0$$$, and $$$3$$$, from left to right. Thus, the sum of squares of radii is $$$13$$$, which is the maximum.

The first line of input contains an integer $$$n$$$, the number of APs ($$$2 \le n \le 3 \cdot 10^5$$$). The second line contains $$$n$$$ distinct space-separated integers in strictly increasing order representing the locations of APs on the line, where the integers are between $$$0$$$ and $$$10^9$$$, inclusive.

Print one integer: the maximum sum of squares of radii of hotspots.

3
0 2 5

13

4
0 1 3 6

10

5
5 7 12 13 15

9