#212. 方差

方差

题目描述

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

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

输入格式

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

输入的第一行包含一个正整数 nn,保证 n104n \le 10^4

输入的第二行有 nn 个正整数,其中第 ii 个数字表示 aia_i 的值。数据保证 1a1a2an1 \le a_1 \le a_2 \le \ldots \le a_n

输出格式

输出到文件 variance.out 中。

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

4
1 2 4 6
52

样例 2

见附加文件中的 variance2.invariance2.ans

样例 3

见附加文件中的 variance3.invariance3.ans

样例 4

见附加文件中的 variance4.invariance4.ans

数据范围

测试点编号 nn\le aia_i\le
131\sim 3 44 1010
454\sim 5 1010 4040
686\sim 8 1515 2020
9129\sim 12 2020 300300
131513\sim 15 5050 7070
161816\sim 18 100100 4040
192219\sim 22 400400 600600
232523\sim 25 1000010000 5050

对于所有数据,保证 n10000,ai600n\le 10000,a_i\le 600