#1442. [NOIP2021] 方差

[NOIP2021] 方差

题目描述

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

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

输入格式

输入的第一行包含一个正整数 nn,保证 n≤104n \le {10}^4。

输入的第二行有 nn 个正整数,其中第 ii 个数字表示 aia_i 的值。数据保证 1≤a1≤a2≤⋯≤an1 \le a_1 \le a_2 \le \cdots \le a_n。

输出格式

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

样例

4
1 2 4 6
52
见附件中的 variance/variance2.in
见附件中的 variance/variance2.ans
见附件中的 variance/variance3.in
见附件中的 variance/variance3.ans
见附件中的 variance/variance4.in
见附件中的 variance/variance4.ans

题目来源:洛谷 P7962