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