题目描述

给定长度为 $n$ 的非严格递增正整数数列 $1 \le a_1 \le a_2 \le \ldots \le a_n$。每次可以进行的操作是：任意选择一个正整数 $1 \lt i \lt 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。 $$

---

输入格式

从文件 variance.in 中读入数据。

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

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

---

输出格式

输出到文件 variance.out 中。

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

---

样例 1

输入

4
1 2 4 6

输出

52

对于 $(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}\left((1-\frac{13}{4})^2+(2-\frac{13}{4})^2+(4-\frac{13}{4})^2+(6-\frac{13}{4})^2\right)=\frac{59}{16}。 $$

• 对于 $(a_1, a_2, a_3, a_4) = (1, 3, 4, 6)$，平均值为 $\frac{7}{2}$，方差为

  $$\frac{1}{4}\left((1-\frac{7}{2})^2+(3-\frac{7}{2})^2+(4-\frac{7}{2})^2+(6-\frac{7}{2})^2\right)=\frac{13}{4}。 $$

• 对于 $(a_1, a_2, a_3, a_4) = (1, 3, 5, 6)$，平均值为 $\frac{15}{4}$，方差为

  $$\frac{1}{4}\left((1-\frac{15}{4})^2+(3-\frac{15}{4})^2+(5-\frac{15}{4})^2+(6-\frac{15}{4})^2\right)=\frac{59}{16}。 $$

---

样例 2

见附加文件中的 variance2.in 与 variance2.ans。

---

样例 3

见附加文件中的 variance3.in 与 variance3.ans。

---

样例 4

见附加文件中的 variance4.in 与 variance4.ans。

---

数据范围

测试点编号	$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$

对于所有数据，保证 $n\le 10000, a_i\le 600$。