$$
\begin{align}
n\overline{a}&=\sum_{i=1}^nai\
\
n^2D
&=n\sum{i=1}^n(ai-\overline{a})^2\
&=n\sum{i=1}^n ai^2-2n\overline{a}\sum{i=1}^n ai+n^2\overline{a}^2\
&=n\sum{i=1}^n ai^2-2(\sum{i=1}^n ai)^2+(\sum{i=1}^n ai)^2\
&=n\sum{i=1}^n ai^2-(\sum{i=1}^n a_i)^2\
\end{align}
$$

观察题目中的式子，$a'i\leftarrow a{i-1}+a_{i+1}-a_i$，根据 CF1110E 的套路，可以差分，令 $di=a{i+1}-a_i(1\leq i\lt n)$，一次操作 $(2\leq i\lt n)$ 即：

$$
d'{i-1}=a'{i}-a'{i-1}=(a{i-1}+a_{i+1}-ai)-a{i-1}=a_{i+1}-a_i=d_i\
d'i=a'{i+1}-a'{i}=a{i+1}-(a{i-1}+a{i+1}-a_i)=ai-a{i-1}=d_{i-1}
$$

相当于交换 $d_{i-1},d_i(2\leq i\lt n)$，故 $d$ 可以通过若干次操作，变为任意 $d$ 的排列。

由于 $a1$ 不变，那么 $a$ 和 $d$ 是一一对应的。现在要求一个 $d$ 的排列使得 $n^2D$ 最小，继续推式子：
$$
\begin{align*}
n^2D
&=n\sum{i=1}^n ai^2-(\sum{i=1}^n ai)^2\
&=n\sum{i=1}^n ai^2-\sum{i=1}^n\sum_{j=1}^na_iaj\
&=\frac{1}{2}(n\sum{i=1}^n ai^2-2\sum{i=1}^n\sum_{j=1}^na_iaj+n\sum{j=1}^n aj^2)\
&=\frac{1}{2}(\sum{i=1}^n\sum_{j=1}^n(a_i-aj)^2)\
&=\sum{i=1}^{n-1}\sum{j=i}^{n-1}(a{j+1}-ai)^2\
&=\sum{i=1}^{n-1}\sum_{j=i}^{n-1}(di+d{i+1}+\cdots+d_j)^2\
\end{align*}
$$
$n^2D$ 取最小值时，$d$ 一定是先递减后递增的。

考虑在分界位置（即递减到递增）从小到大往两边加数，由于
$$
\begin{align}
n^2D
&=n\sum_{i=1}^n ai^2-(\sum{i=1}^n a_i)^2\
\end{align}
$$
维护 $dp[k][s]$ 表示当前已经加入了 $k$ 个数，现在的 $a$ 之和为 $s$ 的最小 $\displaystyle \sum_{i=1}^n a_i^2$。

初始 $dp[1][s]=0$。

转移时考虑加到左边还是右边：

• 左边：原来是 $a_1,a_2,\cdots,a_k$，现在变为 $d,a_1+d,a_2+d,\cdots,a_k+d$，新增的贡献为

$$
\begin{align}
\Delta
&=d^2+\sum_{i=1}^k (d+ai)^2-\sum{i=1}^k ai^2\
&=(k+1)d^2+2d\sum{i=1}^ka_i\
&=(k+1)d^2+2ds\
\end{align}
$$

• 右边：原来是 $a_1,a_2,\cdots,a_k$，现在变为 $a_1,a_2,\cdots,a_k,a_k+d$，新增的贡献为
  $$
  \begin{align}
  \Delta
  &=(a_k+d)^2\
  \end{align}
  $$
  其实可以发现 $a_k$ 是固定的，为之前所有的 $d$ 之和，不需要再记录。

答案为 $\displaystyle \min_s{n\times dp[n][s]-s^2}$。

分析一下时间复杂度，第一维是 $O(n)$ 的，第二维是 $O(nV)$ 的，转移 $O(1)$。

但是可以发现 $d$ 为 $0$ 的转移可以忽略，第一维是 $O(\min(n,V))$ 的，总复杂度为 $O(nV^2)$，可以通过。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1ll<<60;
int n,a[11000],d[11000]; ll dp[510000];
ll sqr(ll x){ return x*x;}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<n;i++) d[i]=a[i+1]-a[i];
    sort(d+1,d+n);

    for (int i=0;i<=500000;i++) dp[i]=INF;
    dp[0]=0; int lim=0,sum=0;
    for (int i=1;i<n;i++){
        if (!d[i]) continue;
        for (int s=lim;s>=0;s--){
            if (dp[s]==INF) continue;
            dp[s+sum+d[i]]=min(dp[s+sum+d[i]],dp[s]+sqr(sum+d[i]));
            dp[s+i*d[i]]=min(dp[s+i*d[i]],dp[s]+2*s*d[i]+i*sqr(d[i]));
            dp[s]=INF;
        }
        lim+=i*d[i]; sum+=d[i];
    }
    ll ans=INF;
    for (int i=0;i<=lim;i++)
        if (dp[i]!=INF) ans=min(ans,n*dp[i]-1ll*i*i);
    printf("%lld\n",ans);
    return 0;
}