You are given a sequence of nondecreasing positive integers $1\le a_1\le a_2\le \cdots \le a_n$.

At each step, you can perform the following operation: Choose any positive integer $1<i<n$, change $a_i$ to $a_{i-1}+a_{i+1}-a_i$.

Determine the minimum variance of the sequence $a$ after performing any number of operations.

The variance is the average of the squared differences between numbers and their mean value. Formally, 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 Specification

The first line contains a positive integer $n$. It is guaranteed that $n\le {10}^4$.

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

Output Specification

Output a single nonnegative integer representing $n^2$ times the minimum variance you determine.

Sample Input

4
1 2 4 6

Sample Output

52

Sample Explanation

For $(a_1,a_2,a_3,a_4)=(1,2,4,6)$, after the first operation, we can get $(1,3,4,6)$. After the second operation, we can get $(1,3,5,6)$. After that we cannot get any new sequence.

For $(a_1,a_2,a_3,a_4)=(1,2,4,6)$, the mean is $\frac{13}{4}$, 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}$, 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}$, 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}$.

Additional Samples

Additional samples can be found here.

Constraints

Test cases	$n\le$	$a_i\le$
$1\sim 3$	$4$	$10$
$4\sim 5$	$10$	$40$
$6\sim 8$	$15$	$20$
$9\sim 12$	$20$	$300$
$13\sim 15$	$50$	$70$
$16\sim 18$	$100$	$40$
$19\sim 22$	$400$	$600$
$23\sim 25$	$10000$	$50$

For all test cases, it is guaranteed that $n\le 10000$, $a_i\le 600$.