Given a non-decreasing sequence of $n$ positive integers $1 \le a_1 \le a_2 \le \dots \le a_n$. The allowed operation is: choose any integer $1 < i < n$, and change $a_i$ to $a_{i-1} + a_{i+1} - a_i$. Find the minimum variance of the sequence after any number of operations. 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 in the sequence and the mean. Formally, the variance 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

The first line 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 \dots \le a_n$.

Output

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

Examples

Input 1

4
1 2 4 6

Output 1

52

Note 1

For $(a_1, a_2, a_3, a_4) = (1, 2, 4, 6)$, the sequence obtained after the first operation is $(1, 3, 4, 6)$, and the sequence obtained after the second operation is $(1, 3, 5, 6)$. No further new sequences 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}$.

Examples 2-4

See the files variance/variance2.in and variance/variance2.ans, variance/variance3.in and variance/variance3.ans, and variance/variance4.in and variance/variance4.ans in the contestant directory.

Constraints

For all data, it is guaranteed that $n \le 10000$ and $a_i \le 600$.