Problem Description

Given a non-strictly increasing sequence of positive integers of length $n$, where $1 \le a_1 \le a_2 \le \cdots \le a_n$. The operation allowed is to choose any integer $1 < i < n$ and change $a_i$ to $a_{i - 1} + a_{i + 1} - a_i$. The goal is to find the minimum variance of the sequence after several such operations, and output the result multiplied by $n^2$.

The definition of variance is the average of the squared differences from the mean. Formally, the variance $D$ is defined as $D = \frac{1}{n} \sum_{i = 1}^{n} (a_i - \bar{a})^2$, where $\bar{a} = \frac{1}{n} \sum_{i = 1}^{n} a_i$.

Input Format

The first line of input contains a positive integer $n$, where $n \le 10^4$.

The second line contains $n$ positive integers, where the $i$-th number represents the value of $a_i$. It is guaranteed that $1 \le a_1 \le a_2 \le \cdots \le a_n$.

Output Format

Output a single line containing a non-negative integer, which is the minimum variance multiplied by $n^2$.

Sample Input and Output

Sample Input #1

4
1 2 4 6

Sample Output #1

52

Sample Input #2

See the attached file variance/variance2.in

Sample Output #2

See the attached file variance/variance2.ans

Sample Input #3

See the attached file variance/variance3.in

Sample Output #3

See the attached file variance/variance3.ans

Sample Input #4

See the attached file variance/variance4.in

Sample Output #4

See the attached file variance/variance4.ans

Notes

[Sample Explanation #1]

For the sequence $(a_1, a_2, a_3, a_4) = (1, 2, 4, 6)$, the sequence after the first operation could be $(1, 3, 4, 6)$, and after the second operation, it could be $(1, 3, 5, 6)$. No new sequences can be obtained after this.

For $(a_1, a_2, a_3, a_4) = (1, 2, 4, 6)$, the mean is $\frac{13}{4}$ and the variance is $\frac{1}{4}((1 - \frac{13}{4})^2 + (2 - \frac{13}{4})^2 + (4 - \frac{13}{4})^2 + (6 - \frac{13}{4})^2) = \frac{59}{16}$.

For $(a_1, a_2, a_3, a_4) = (1, 3, 4, 6)$, the mean is $\frac{7}{2}$ and the variance is $\frac{1}{4}((1 - \frac{7}{2})^2 + (3 - \frac{7}{2})^2 + (4 - \frac{7}{2})^2 + (6 - \frac{7}{2})^2) = \frac{13}{4}$.

For $(a_1, a_2, a_3, a_4) = (1, 3, 5, 6)$, the mean is $\frac{15}{4}$ and the variance is $\frac{1}{4}((1 - \frac{15}{4})^2 + (3 - \frac{15}{4})^2 + (5 - \frac{15}{4})^2 + (6 - \frac{15}{4})^2) = \frac{59}{16}$.

[Data Range]

For all data, it is guaranteed that $1 \le n \le 10^4$ and $1 \le a_i \le 600$.

见题面 Input 部分

见题面 Output 部分