방송국

$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$ 에 전달해서 $h$ 번 만에 $s\_i$ 의 방송이 $s\_j$ 에 전달될 수 있다. 물론 $h=1$ 인 경우 는 $s\_i$ 의 방송이 직접 $s\_j$ 에 전달되는 경우이다. 이런 경우들에 대해 $s\_i$ 의 방송이 $h$ -단계에 $s\_j$ 에 전달된다고 말한다.

우리는 방송국들 중에 하나의 방송국을 정하고 싶다. 이 방송국은 방송하지 않고 단지 다른 모든 방송국들로부터 많아야 $h$ -단계 만에 그들의 방송을 받아야 한다. 이 방송국을 $h$ -집중국 이라고 한다. $h$ -집중국의 방송 전파 범위는 $0$ 이라 할 수 있다.

각 방송국 $s\_i$ 에 전파 범위 $r\_i$ 를 할당할 때, 할당 비용을 전파 범위의 제곱의 합으로 정의한다. 다시 말해서 비용은 $\displaystyle\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$ 을 가진다. 그러면 $18$ 이 모든 가능한 $h$ -집중국들에 대한 최소 비용들 중 최솟값이다.

그림 1

그림 2

여러분은 관리자를 위해 다음 한 가지 함수를 구현해야만 한다.

void stations(int N, int X[]) ; 방송국들의 개수 $N$ , 각 방송국의 위치를 나타내는 $X\[0..N-1]$ 를 인자로 받는다. 여기서, $X\[]$ 는 크기 $N$ 인 벡터(vector)이고, $X\[i]$ 의 값은 모두 다르고 오름차순으로 저장되어 있다.

여러분은 stations() 함수 안에서 다음 함수를 사용하여 답을 제출하여야 한다.

void answer(long long Y[]) : 크기 $N-1$ 인 벡터 $Y\[]$ 를 제출하는 함수이다. $i=0,\dots, N-2$ 에 대해서, $Y\[i]$ 의 값은 모든 가능한 $(i+1)$ -집중국들의 최소비용의 최솟 값이다. 이 함수는 stations() 함수 안에서 정확히 한 번 호출되어야 한다.

문제

제한