思路与算法

令相邻差 $d_i=a_{i+1}-a_i\ge0$。一次操作恰好交换 $d_{i-1},d_i$，因此所有差的任意排列都能到达。整体平移不影响方差，可固定第一个数为0。设前缀坐标的和为 $p$、平方和为 $Q$，答案就是 $nQ-p^2$。

最优差序可取V形，即先非增、再非减。因此按差值从小到大处理，把每组相同差分配到当前序列左右两端。零差先合并：若有 $z$ 个零差，初态为 $c=z+1$ 个重合点，跨度 $L=0$，$p=Q=0$。状态 $dp[p]$ 记录固定当前点数 $c$、跨度 $L$ 时的最小平方和 $Q$；相同 $p$ 下只保留最小 $Q$，未来变换中其他部分只依赖 $p$，所以此压缩安全。

考虑差值 $x$ 出现 $q$ 次，左端放 $k$ 次、右端放 $q-k$ 次。定义 $H=(c-1)x-L$，$C=qL+xq(q+1)/2$，$A=L^2+Lx$， $D=qL^2+Lxq(q+1)+x^2q(q+1)(2q+1)/6$。 直接累加新点坐标可得 $p'=p+C+kH$， $Q'=Q+D+2kx p-kA+k^2xH$。

若 $H=0$，当前必为单个点且没有已处理差；这一组产生唯一等距点集，直接初始化 $p'=C,Q'=D$。其余情况 $H>0$。令 $u=p'-C$，消去 $k$ 得 $H Q'-x u^2+A u=H Q-x p^2+A p+H D$。 对于固定余数 $p\bmod H$，新坐标 $u$ 的候选旧坐标为 $u,u-H,\ldots,u-qH$。维护评分 $Hdp[p]-xp^2+Ap$ 的长度 $q+1$ 滑动窗口最小值即可，一次处理整组，无须对每个旧状态再枚举全部 $k$。处理完后更新 $c\leftarrow c+q,L\leftarrow L+qx$。最后枚举所有有限状态，取 $n dp[p]-p^2$ 的最小值。

正确性说明

操作与差排列。 修改 $a_i$ 后，左差变为原右差、右差变为原左差，其他差不变。相邻交换生成任意排列；所有差非负，故整个过程中数列仍单调且端点不变。平移不改方差，目标展开确为 $nQ-p^2$。

V形性质。 假设全局最优差序包含内峰：连续 $t\ge1$ 个相等正差 $x$，两边的差为 $a<x,b<x$。交换左边界相邻差，只把一个前缀坐标 $s_l$ 增加 $\delta=x-a>0$；交换右边界，只把另一个前缀坐标 $s_r$ 减少 $\varepsilon=x-b>0$。这两个前缀相距 $s_r-s_l=tx$。若一个坐标 $s$ 改变 $h$，目标的变化为 $h[2(ns-p)+(n-1)h]$。最优性要求两次交换的变化都非负，于是 $2(ns_l-p)\ge-(n-1)(x-a)$， $2(ns_r-p)\le(n-1)(x-b)$。 相减得到 $2ntx\le(n-1)(2x-a-b)$，整理为 $2[n(t-1)+1]x+(n-1)(a+b)\le0$，与 $x>0,a,b\ge0$ 矛盾。因此不存在内峰或高平台。没有内峰平台的序列必为先非增后非减的V形。

状态覆盖与分组。 V形差序中，所有最小差位于中央；每加入一个更大差，只能放到已处理差序两端。同组相同差放左 $k$ 个，其余放右，恰好覆盖所有V形排列。零差均聚在中央，初态处理不漏解。对固定 $p$，较大 $Q$ 在任何后续分组中仍会保持较大，故只保留最小平方和不丢失最优。

滑窗等价。 新序列中旧点整体右移 $kx$，新增左点坐标为 $0,x,\ldots,(k-1)x$，新增右点为 $kx+L+x,\ldots,kx+L+(q-k)x$，求和即得两条分组公式。它们消去 $k$ 后得到评分恒等式。固定余数时，$0\le k\le q$ 等价于旧坐标落在长度 $q+1$ 的等步长窗口中，所以单调队列返回的最小评分与逐个枚举 $k$ 完全一致。由组数归纳，最终DP覆盖全部最优差序，取目标最小值即为答案。

复杂度

记总跨度 $S=a_n-a_1\le599$，正差不同值数为 $g$。因为这些不同正整数之和不超过 $S$，有 $g(g+1)/2\le S$，从而 $g\le34$。初始化读入和差值计数为 $O(n+600)$。第 $j$ 组所有余数链扫描的总长度为 $O(n S_j)$，其中 $S_j$ 为当前跨度，单调队列每个位置至多入队、出队一次。因此总时间 $O(n\sum_j S_j)$，可宽松写为 $O(gnS)$；零差无论多少都只形成一个初态，不额外增加组数。空间为两个DP数组，$O(nS)$，另含常数大小差值计数与一条余数链的队列。所有目标、评分和中间乘积用64位有符号整数；按 $n\le10^4,S\le599$ 的全局上界，最大中间量小于 $10^{17}$。

易错点

不能直接枚举所有差排列，也不能只对小 $n$ 搜索后把大数据当作已解决。V形性质需要交换证明，不能凭经验交替摆放。零差造成大量重复坐标，必须计入点数 $c$，不能删掉这些点。$H=0$ 时不能做余数或除法；该组用等距点集直接初始化。评分变换中的 $p$ 与 $u=p'-C$ 不能混用，窗口过期条件是旧坐标小于 $u-qH$。不可达状态应跳过，不能把无穷大带入乘法。答案是 $nQ-p^2$，不是 $Q-p^2$。题面方差定义的求和下标排版有误，按 $n$ 个数的定义解释。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4000000000000000000LL;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n))
        return 0;
    vector<int> count(600);
    int previous;
    cin >> previous;
    for (int i = 1; i < n; ++i) {
        int a;
        cin >> a;
        ++count[a - previous];
        previous = a;
    }
    int c = count[0] + 1, L = 0, lo = 0, hi = 0;
    vector<ll> dp(1, 0);
    for (int x = 1; x < 600; ++x)
        if (count[x]) {
            int q = count[x];
            ll H = 1LL * (c - 1) * x - L;
            ll C = 1LL * q * L + 1LL * x * q * (q + 1) / 2;
            ll A = 1LL * L * L + 1LL * L * x;
            ll D = 1LL * q * L * L + 1LL * L * x * q * (q + 1) +
                   1LL * x * x * q * (q + 1) * (2 * q + 1) / 6;
            if (H == 0) {
                lo = hi = (int)C;
                dp.assign(hi + 1, INF);
                dp[hi] = D;
                c += q;
                L += q * x;
                continue;
            }
            int zmax = hi + q * H;
            vector<ll> next((int)C + zmax + 1, INF);
            vector<int> queue((hi - lo) / H + q + 4);
            vector<ll> val(queue.size());
            int nlo = INT_MAX, nhi = 0;
            for (int r = 0; r < H && r <= zmax; ++r) {
                int head = 0, tail = 0;
                int start = r;
                if (start < lo)
                    start += (lo - start + H - 1) / H * H;
                for (int z = start; z <= zmax; z += H) {
                    while (head < tail && queue[head] < z - q * H)
                        ++head;
                    if (z <= hi && dp[z] != INF) {
                        ll score = H * dp[z] - 1LL * x * z * z + A * z;
                        while (head < tail && val[tail - 1] >= score)
                            --tail;
                        queue[tail] = z;
                        val[tail++] = score;
                    }
                    if (head < tail) {
                        int p = C + z;
                        ll Q = (val[head] + H * D + 1LL * x * z * z - A * z) / H;
                        next[p] = Q;
                        nlo = min(nlo, p);
                        nhi = max(nhi, p);
                    }
                }
            }
            next.resize(nhi + 1);
            dp.swap(next);
            lo = nlo;
            hi = nhi;
            c += q;
            L += q * x;
        }
    ll answer = INF;
    for (int p = lo; p <= hi; ++p)
        if (dp[p] != INF)
            answer = min(answer, 1LL * n * dp[p] - 1LL * p * p);
    cout << answer << '\n';
}