C-[NOIP2021]方差（variance）_NOIP2021提高组复赛（官方数据）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定长度为n的非严格递增正整数数列 $1≤a_1 ≤a_2 ≤· · ·≤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}\left(a_{i}-\bar{a}\right)^{2}$ ，其中 $\bar{a}=\frac{1}{n} \sum_{i=1}^{n} a_{i}$ 。

输入描述:

输入的第一行包含一个正整数 $n$ ，保证 $n≤10^4$ 。

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

输出描述:

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

示例1

输入

复制

4 
1 2 4 6

输出

复制

说明

对于 ，第一次操作得到的数列有  ，第二次操作得到的新的数列有 。之后无法得到新的数列。
对于 ，平均值为，方差为。

备注:

对于所有的数据，保证 。