방송국

$N$개의 방송국 $s\_1, s\_2, \dots, s\_N$이 직선 위에 있다. 방송국 $s\_i$의 위치는 양의 정수 $x\_i$로 주어진다. 각 방송국 $s\_i$에 방송 전파 범위 $r\_i$를 할당해야 한다. 방송국 $s\_i$가 방송하면, $s\_i$로부터 거리 $r\_i$ 이내에 있는 방송국들은 $s\_i$의 방송 전파를 받을 수 있다. 즉, 방송국 $s\_j$가 닫힌구간 $[x\_i-r\_i,x\_i+r\_i]$ 안에 있으면 $s\_j$는 $s\_i$의 방송 전파를 받을 수 있다. 방송국 $s\_i$의 방송은 $h-1$ ($h > 1$)개의 방송국이 이어서 전달해 방송국 $s\_j$에 닿을 수 있다. 즉, 방송국 $s\_{i\_1}, s\_{i\_2}, \dots, s\_{i\_{h-1}}$이 존재하여 $s\_i$의 방송이 $s\_{i\_1}$에 전달되고, 각 $s\_{i\_k}$가 $s\_{i\_{k+1}}$로 전달하고, $s\_{i\_{h-1}}$이 $s\_j$에 전달하면, $s\_i$의 방송은 $h$번 만에 $s\_j$에 전달될 수 있다. 물론 $h=1$이면 $s\_i$의 방송이 $s\_j$에 직접 전달되는 경우이다. 이런 경우에 $s\_i$의 방송이 $h$단계에 $s\_j$에 전달된다고 말한다. 우리는 방송국 중 하나를 골라 $h$-집중국으로 정하고 싶다. 이 방송국은 방송하지 않고, 다른 모든 방송국의 방송을 많아야 $h$단계 만에 받아야 한다. 이 방송국을 $h$-집중국이라고 한다. $h$-집중국의 방송 전파 범위는 $0$으로 본다. 각 방송국 $s\_i$에 전파 범위 $r\_i$를 할당할 때, 할당 비용은 전파 범위 제곱의 합으로 정의한다. 즉, 비용은 $\sum\_{i=1}^{N}{r\_i^2}$이다. 이 비용이 최소가 되도록 전파 범위를 할당한다. 방송국 $s$가 $h$-집중국일 때 최소 할당 비용을 $C\_h^\*(s)$로 나타내면, 문제의 목표는 가능한 모든 $h$-집중국 $s$에 대한 $C\_h^\*(s)$ 중 최솟값을 찾는 것이다. 즉, 그 최솟값을 가지는 $h$-집중국과 그 최소 비용을 주는 전파 범위 할당을 찾는다. $N$개 방송국의 위치가 주어질 때, 각 $h=1, 2, \dots, N-1$에 대해 가능한 모든 $h$-집중국 $s$의 최소 할당 비용 $C\_h^\*(s)$의 최솟값을 출력하는 프로그램을 작성하시오. 예를 들어, 아래 그림 1과 2는 $5$개의 방송국 $s\_1, \dots, s\_5$가 각각 좌표 $1, 3, 4, 6, 9$에 위치하고 $h=2$인 경우이다. 그림 1처럼 $s\_1, s\_2, s\_3, s\_4$에 각각 $3, 1, 5, 2$의 전파 범위를 할당하면 $s\_5$가 $h$-집중국인 경우의 최소 비용은 $39$이다. 그림 2처럼 $s\_1, s\_2, s\_4, s\_5$에 각각 $2, 1, 2, 3$의 전파 범위를 할당하면 $s\_3$이 $h$-집중국인 경우의 최소 비용은 $18$이다. 따라서 가능한 모든 $h$-집중국의 최소 비용 중 최솟값은 $18$이다. 그림 1 그림 2

관리자를 위해 다음 함수를 구현해야 한다. void stations(int N, int X[]) ; 함수는 방송국 수 $N$과 각 방송국의 위치를 나타내는 $X\[0..N-1]$를 인자로 받는다. 여기서 $X\[]$는 크기가 $N$인 벡터이고, $X\[i]$의 값은 모두 다르며 오름차순으로 저장되어 있다. stations() 함수 안에서는 다음 함수로 답을 제출해야 한다. void answer(long long Y[]) 함수는 크기 $N-1$인 벡터 $Y\[]$를 제출한다. $i=0,\dots,N-2$에 대해 $Y\[i]$의 값은 가능한 모든 $(i+1)$-집중국의 최소 비용 중 최솟값이다. 이 함수는 stations() 함수 안에서 정확히 한 번 호출되어야 한다.

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