Problem Description

Given a non-strictly increasing sequence of positive integers of length $n$: $1 \le a_1 \le a_2 \le \cdots \le a_n$. In each operation, you may choose any positive integer $1 < i < n$ and change $a_i$ to $a_{i - 1} + a_{i + 1} - a_i$. After performing some operations, find the minimum possible variance of the sequence. Output the result of the minimum variance multiplied by $n^2$.

The variance is defined as the average of the squared differences between each number and the mean. More formally, the variance is $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 contains a positive integer $n$, and it is guaranteed that $n \le {10}^4$.

The second line contains $n$ positive integers, where the $i$-th number is $a_i$. The testdata guarantees 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 you can obtain multiplied by $n^2$.

4
1 2 4 6

52

见附件中的 variance/variance2.in

见附件中的 variance/variance2.ans

见附件中的 variance/variance3.in

见附件中的 variance/variance3.ans

见附件中的 variance/variance4.in

见附件中的 variance/variance4.ans

Hint

Sample Explanation #1

For $(a_1, a_2, a_3, a_4) = (1, 2, 4, 6)$, after the first operation, the possible sequence is $(1, 3, 4, 6)$. After the second operation, the new sequence is $(1, 3, 5, 6)$. After that, no new sequence can be obtained.

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}$.

Constraints

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

Translated by ChatGPT 5