You are given a sequence of nondecreasing positive integers ~1 \le a_1 \le a_2 \le \dots \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-\overline a)^2~ where ~\overline 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 \dots \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~	~10\,000~	~50~

For all test cases, it is guaranteed that ~n \le 10\,000~, ~a_i \le 600~.