Broadcasting Stations

There are $N$ broadcasting stations $s\_1, s\_2, \dots, s\_N$ on a straight line. The position of station $s\_i$ is a positive integer $x\_i$. You must assign a broadcast range $r\_i$ to each station $s\_i$. When station $s\_i$ broadcasts, the stations within distance $r\_i$ of $s\_i$ can receive its signal. In other words, if station $s\_j$ lies in the closed interval $[x\_i-r\_i,x\_i+r\_i]$, then $s\_j$ can receive the broadcast of $s\_i$. A broadcast from station $s\_i$ can reach station $s\_j$ in $h$ steps, where $h > 1$, by being relayed through $h-1$ stations. That is, there exist stations $s\_{i\_1}, s\_{i\_2}, \dots, s\_{i\_{h-1}}$ such that $s\_i$ passes the broadcast to $s\_{i\_1}$, each $s\_{i\_k}$ passes it to $s\_{i\_{k+1}}$, and $s\_{i\_{h-1}}$ passes it to $s\_j$. Then the broadcast of $s\_i$ reaches $s\_j$ in $h$ steps. Of course, when $h=1$, the broadcast of $s\_i$ reaches $s\_j$ directly. In these cases, we say that the broadcast of $s\_i$ reaches $s\_j$ in $h$ steps. We want to choose one station as an $h$-center. This station does not broadcast. It must receive the broadcasts of all other stations within at most $h$ steps. We call this station an $h$-center. The broadcast range of an $h$-center is $0$. When assigning a range $r\_i$ to each station $s\_i$, the cost of the assignment is the sum of the squares of the ranges. That is, the cost is $\sum\_{i=1}^{N}{r\_i^2}$. We assign the ranges so that this cost is minimized. Let $C\_h^\*(s)$ be the minimum cost when $s$ is an $h$-center. The goal is to find the $h$-center with the smallest $C\_h^\*(s)$ among all possible $h$-centers $s$, together with the range assignment that achieves that minimum cost. Given the positions of $N$ stations, write a program that outputs, for each $h=1, 2, \dots, N-1$, the minimum value of $C\_h^\*(s)$ over all possible $h$-centers $s$. For example, Figures 1 and 2 below show the case where five stations $s\_1, \dots, s\_5$ are at coordinates $1, 3, 4, 6, 9$ and $h=2$. In Figure 1, assigning the ranges $3, 1, 5, 2$ to $s\_1, s\_2, s\_3, s\_4$ gives a minimum cost of $39$ when $s\_5$ is the $h$-center. In Figure 2, assigning the ranges $2, 1, 2, 3$ to $s\_1, s\_2, s\_4, s\_5$ gives a minimum cost of $18$ when $s\_3$ is the $h$-center. So the smallest minimum cost over all possible $h$-centers is $18$. Figure 1. Figure 2.

You must implement the following function for the administrator. void stations(int N, int X[]) ; takes the number of stations $N$ and the array $X\[0..N-1]$ of station positions. Here $X\[]$ is a vector of size $N$, the values of $X\[i]$ are all distinct, and they are stored in ascending order. Inside the stations() function, you must submit your answer with the following function. void answer(long long Y[]) submits a vector $Y\[]$ of size $N-1$. For $i=0,\dots,N-2$, $Y\[i]$ is the minimum over all possible $(i+1)$-centers of their minimum cost. This function must be called exactly once inside the stations() function.

$2 \le N \le 120$, $1 \le x\_1 < x\_2 < \cdots < x\_N \le 10^8$