题目描述
给定长度为 n 的非严格递增正整数数列 1≤a1≤a2≤…≤an。每次可以进行的操作是:任意选择一个正整数 1<i<n,将 ai 变为 ai−1+ai+1−ai。求在若干次操作之后,该数列的方差最小值是多少。请输出最小值乘以 n2 的结果。
其中方差的定义为:数列中每个数与平均值的差的平方的平均值。更形式化地说,方差的定义为 D=n1∑i=1n(ai−a)2,其中 a=n1∑i=1nai。
输入格式
从文件 variance.in
中读入数据。
输入的第一行包含一个正整数 n,保证 n≤104。
输入的第二行有 n 个正整数,其中第 i 个数字表示 ai 的值。数据保证 1≤a1≤a2≤…≤an。
输出格式
输出到文件 variance.out
中。
输出仅一行,包含一个非负整数,表示你所求的方差的最小值的 n2 倍。
样例 1
4
1 2 4 6
52
对于 (a1,a2,a3,a4)=(1,2,4,6),第一次操作得到的数列有 (1,3,4,6),第二次操作得到的新的数列有 (1,3,5,6)。之后无法得到新的数列。
对于 (a1,a2,a3,a4)=(1,2,4,6),平均值为 413,方差为 41((1−413)2+(2−413)2+(4−413)2+(6−413)2)=1659。
对于 (a1,a2,a3,a4)=(1,3,4,6),平均值为 27,方差为 41((1−27)2+(3−27)2+(4−27)2+(6−27)2)=413。
对于 (a1,a2,a3,a4)=(1,3,5,6),平均值为 415,方差为 41((1−415)2+(3−415)2+(5−415)2+(6−415)2)=1659。
样例 2
见附加文件中的 [variance2.in
](file:variance2.in) 与 [variance2.ans
](file:variance2.ans)。
样例 3
见附加文件中的 [variance3.in
](file:variance3.in) 与 [variance3.ans
](file:variance3.ans)。
样例 4
见附加文件中的 [variance4.in
](file:variance4.in) 与 [variance4.ans
](file:variance4.ans)。
数据范围
测试点编号 |
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,ai≤600。