给定长度为 $n$ 的非严格递增正整数数列 $1\le a_1\le a_2\le \cdots \le a_n$。每次可以进行的操作是：任意选择一个正整数 $1<i<n$，将 $a_i$ 变为 $a_{i-1}+a_{i+1}-a_i$。求在若干次操作之后，该数列的方差最小值是多少。请输出最小值乘以 $n^2$ 的结果。

其中方差的定义为：数列中每个数与平均值的差的平方的平均值。更形式化地说，方差的定义为 $D=\frac{1}{n}\sum _{i=1}^n{(a_i-\overline{a})}^2$，其中 $\overline{a}=\frac{1}{n}\sum _{i=1}^n{a}_i$。

输入格式

输入的第一行包含一个正整数 $n$，保证 $n\le {10}^4$。

输入的第二行有 $n$ 个正整数，其中第 $i$ 个数字表示 $a_i$ 的值。数据保证 $1\le a_1\le a_2\le \cdots \le a_n$。

输出格式

输出仅一行，包含一个非负整数，表示你所求的方差的最小值的 $n^2$ 倍。

样例一

input

4
1 2 4 6

output

52

explanaiton

对于 $(a_1,a_2,a_3,a_4)=(1,2,4,6)$，第一次操作得到的数列有 $(1,3,4,6)$，第二次操作得到的新的数列有 $(1,3,5,6)$。之后无法得到新的数列。

对于 $(a_1,a_2,a_3,a_4)=(1,2,4,6)$，平均值为 $\frac{13}{4}$，方差为 $\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}$。

对于 $(a_1,a_2,a_3,a_4)=(1,3,4,6)$，平均值为 $\frac{7}{2}$，方差为 $\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}$。

对于 $(a_1,a_2,a_3,a_4)=(1,3,5,6)$，平均值为 $\frac{15}{4}$，方差为 $\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}$。

样例二、三

见附件下载。

数据范围

对于所有的数据，保证 $1\le n\le {10}^4$，$1\le a_i\le 600$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$