There are $N$ broadcasting stations $s_1, s_2, \dots, s_N$ located on a straight line. The position of station $s_i$ is given as a positive integer $x_i$. You must assign a broadcast range $r_i$ to each station $s_i$. When station $s_i$ broadcasts, all stations within distance $r_i$ from $s_i$ can receive the broadcast. In other words, a station $s_j$ can receive the broadcast from $s_i$ if it is located in the closed interval $[x_i - r_i, x_i + r_i]$.

The broadcast from station $s_i$ can be delivered to station $s_j$ by being relayed through $h-1$ ($h > 1$) stations. That is, there exist stations $s_{i_1}, s_{i_2}, \dots, s_{i_{h-1}}$ such that $s_i$ transmits its broadcast to $s_{i_1}$, each $s_{i_k}$ transmits to $s_{i_{k+1}}$, and $s_{i_{h-1}}$ transmits to $s_j$, so that the broadcast of $s_i$ is delivered to $s_j$ in $h$ steps. Of course, if $h=1$, the broadcast of $s_i$ is delivered directly to $s_j$. In such cases, we say that the broadcast of $s_i$ is delivered to $s_j$ in $h$ steps.

We want to choose one station among the broadcasting stations. This station does not broadcast, but must receive broadcasts from all other stations in at most $h$ steps. This station is called an $h$-hub. The broadcast range of an $h$-hub is 0.

When assigning a broadcast range $r_i$ to each station $s_i$, the assignment cost is defined as the sum of the squares of the broadcast ranges. In other words, the cost is given by $\sum_{i=1}^N r_i^2$. We will assign the broadcast ranges such that this cost is minimized. If station $s_i$ is an $h$-hub, let the minimum assignment cost be denoted by $C_h^*(s_i)$. The goal of the problem is to find the $h$-hub that has the minimum value among all possible $C_h^*(s_i)$ for all possible $h$-hubs, and the broadcast range assignment that yields this minimum cost.

Given the positions of $N$ broadcasting stations, for each $h = 1, 2, \dots, N-1$, write a program that outputs the minimum value of $C_h^*(s_i)$ for all possible $h$-hubs $s_i$.

For example, consider 5 stations $s_1, \dots, s_5$ located at coordinates $1, 3, 4, 6, 9$ as shown in Figure 1 and Figure 2, with $h=2$. In this case, as shown in Figure 1, when assigning broadcast ranges $3, 1, 5, 2$ to $s_1, s_2, s_4, s_5$ respectively, the minimum cost when $s_3$ is a 2-hub is 39. As shown in Figure 2, when assigning broadcast ranges $2, 1, 2, 3$ to $s_1, s_2, s_4, s_5$ respectively, the minimum cost when $s_3$ is a 2-hub is 18. Then 18 is the minimum of the minimum costs for all possible 2-hubs.

You must implement the following function for the administrator.

• void stations(int N, int X[]): Receives $N$, the number of broadcasting stations, and $X[0..N-1]$, representing the position of each station. Here, $X[]$ is a vector of size $N$, and the values of $X[i]$ are all distinct and stored in ascending order.

You must submit your answer using the following function within the stations() function.

• void answer(long long Y[]): A function to submit a vector $Y[]$ of size $N-1$. For $i=0, \dots, N-2$, the value of $Y[i]$ is the minimum of the minimum costs of all possible $(i+1)$-hubs. This function must be called exactly once within the stations() function.

Implementation Details

You must submit exactly one file named stations.cpp. This file must implement the following function:

void stations(int N, int X[]);

This function must operate as described above. Of course, you may create and use other functions internally. The submitted code must not perform input/output or access other files.

Grader

The provided grader reads the input in the following format:

• line 1: $N$ (number of broadcasting stations)
• line 2: $N$ integers $x_1, x_2, \dots, x_N$ (positions of the stations)

The provided grader outputs the minimum value of the minimum costs for all possible $i$-hubs on the $i$-th line for each $i=1, \dots, N-1$.

Constraints

• $2 \le N \le 120$.
• $1 \le x_1 < x_2 < \dots < x_N \le 10^8$.

Subtasks

• Subtask 1 [11 points]: $N \le 7$.
• Subtask 2 [21 points]: $N \le 30$.
• Subtask 3 [17 points]: $N \le 60$.
• Subtask 4 [51 points]: No additional constraints.

Examples

Input 1

3
1 3 8

Output 1

29
29

Input 2

5
1 3 4 6 9

Output 2

39
18
18
18

Figure 1. Broadcast range assignment for 5 stations with s3 as a 2-hub (cost 39)