题目描述

给定长度为 $n$ 的非严格递增正整数数列 $1 ≤ a_1 ≤ a_2 ≤ · · · ≤ 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 ≤ 10^4$。 输入的第二行有 $n$ 个正整数，其中第 $i$ 个数字表示 $a_i$ 的值。数据保证 $1 ≤ a-1 ≤a_2 ≤ · · · ≤ a_n$。

输出

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

输入样例

4
1 2 4 6

输出样例

52

提示

【样例 1 解释】 对于 ($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}$。 【数据范围】

测试点编号	n ≤	ai ≤
1 ∼ 3	4	10
4 ∼ 5	10	40
6 ∼ 8	15	20
9 ∼ 12	20	300
13 ∼ 15	50	70
16 ∼ 18	100	40
19 ∼ 22	400	600
23 ∼ 25	10000	50

对于所有的数据，保证 $n ≤ 10000$，$a_i ≤ 600$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共7个测试点，非原站或官方原始数据。总分100分。