UOJ Logo Universal Online Judge

UOJ

#690. 【NOIP2021】方差

附件下载 统计

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

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

输入格式

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

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

输出格式

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

样例一

input

4
1 2 4 6

output

52

explanaiton

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

对于 $(a_1, a_2, a_3, a_4) = (1, 3, 4, 6)$,平均值为 $\frac{7}{2}$,方差为 $\frac{1}{4} ({(1 - \frac{7}{2})}^2 + {(3 - \frac{7}{2})}^2 + {(4 - \frac{7}{2})}^2 + {(6 - \frac{7}{2})}^2) = \frac{13}{4}$。

对于 $(a_1, a_2, a_3, a_4) = (1, 3, 5, 6)$,平均值为 $\frac{15}{4}$,方差为 $\frac{1}{4} ({(1 - \frac{15}{4})}^2 + {(3 - \frac{15}{4})}^2 + {(5 - \frac{15}{4})}^2 + {(6 - \frac{15}{4})}^2) = \frac{59}{16}$。

样例二、三

见附件下载。

数据范围

测试点编号 $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$ ${10}^4$ $50$

对于所有的数据,保证 $1 \le n \le {10}^4$,$1 \le a_i \le 600$。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$