这题可以把通常的 $O(n^2V)$ 动态规划进一步降到 $O(K+Vn^{\omega-1})$：其中 $K=n+\sum_i|S_i|$ 是输入规模，$V$ 是坐标值域的宽度，$\omega>2$ 是所采用的普通方阵乘法算法的指数。当 $V=\Theta(n)$ 时，这就是 $O(n^\omega)$，严格优于三次复杂度。

关键不只是求出一个数组的最优值，还要把所有数组的求和写成一种具有平移不变性的网格动态规划，再用四叉分治批量处理状态。以下给出完整推导。题面中的限制是 $n\le 400$、坐标属于 $[0,800]$，答案对 $998244353$ 取模。

单个数组的最优值

对于固定的非降数组 $a$，令 $b_i=a_i-i$。最终有一个相当简洁的结论：

$$ \boxed{F(a)=\max\left(0,\ \max_i b_i-\min_i b_i-n+1\right).} $$

先证明这个结论，尤其是其中“下界一定能够达到”的部分。

任取 $i< j$。选择编号严格位于 $(i,j)$ 内的人时，$i,j$ 两人的距离至多减少 $2$；选择其他人时，这个距离至多减少 $1$。人的相对顺序始终不会改变，所以这一判断在整个操作过程中都成立。因此，最终直径至少为 $a_j-a_i-n-(j-i-1)$，也就是 $b_j-b_i-n+1$。

为了证明这些下界已经充分，考虑一个更一般的中间状态：当前坐标为 $x_1\le\cdots\le x_n$，还没有被选择过的人的集合为 $U$，$m=|U|$，并令 $u(i,j)=|U\cap{i+1,\ldots,j-1}|$。定义势函数 $\Phi=\max\bigl(0,\max_{i< j}(x_j-x_i-m-u(i,j))\bigr)$。同样的计数说明，$\Phi$ 是剩余操作结束后的直径下界。

下面证明：只要还有人没有被选过，就可以选择一个人，使操作后的 $\Phi$ 不增加。

把满足 $x_j-x_i-m-u(i,j)=\Phi$ 的区间称为临界区间，并将它看成坐标轴上的闭区间 $[x_i,x_j]$。

这些临界区间有公共交集。否则，区间的性质保证其中存在两个不相交的区间，设为 $[x_i,x_j]$ 和 $[x_k,x_\ell]$，其中 $x_j< x_k$。将它们合并成 $[x_i,x_\ell]$，新增的内部未选人数不超过 $m$，于是合并后对应的表达式至少为 $2\Phi+(x_k-x_j)>\Phi$，矛盾。

它们的公共交集中一定存在一个尚未选过的人。理由是，临界区间的左端点若既不是全局最左坐标，该坐标上又没有未选者，就可以向左扩张到最近一个未选者，或全局最左端；取适当的端点编号后，内部未选人数不变，长度却严格增加，矛盾。右端点同理。因此，公共交集的端点要么提供一个未选者，要么公共交集已经覆盖整个坐标范围。

选择公共交集内的一个未选者 $p$。对于任意临界区间：

如果 $p$ 的坐标严格位于区间内部，距离和剩余可缩短量都减少 $2$。如果 $p$ 位于端点坐标，距离和剩余可缩短量都减少 $1$。这里不存在“$p$ 的坐标等于端点，但编号被严格计入内部”的情况，否则把该端点收缩到 $p$，就能将临界表达式再增大至少 $1$。

所以所有临界表达式都不会增加。对于其他正长度区间，一次操作至多让表达式增加 $1$；由于所有量都是整数，它们也不会超过原来的 $\Phi$。零长度区间对应的表达式始终非正。若原来根本不存在临界区间，任选一个未选者也满足同样的结论。

不断执行上述选择，直至 $m=0$。此时 $\Phi$ 就等于实际直径，从而下界可以达到。代回初始状态，得到 $F(a)=\max\bigl(0,\max_{i< j}(b_j-b_i)-n+1\bigr)$。

最后注意，对于 $i< j$，有 $b_i-b_j=(a_i-a_j)+(j-i)\le n-1$。因此，当整个 $b$ 数组的极差大于 $n-1$ 时，最大值不可能出现在最小值之前；当极差不超过 $n-1$ 时，答案直接为 $0$。这就证明了开头的公式。

例如 $a=(0,1,1,1,10)$ 时，$b=(-1,-1,-2,-3,5)$，所以 $F(a)=8-4=4$。直接用初始直径减去 $2n-2$ 会得到错误的 $2$，因为靠近端点的重合会使一些操作无法同时缩短两侧距离。

把答案改写成反射状态机

闭式虽然简单，但直接枚举 $\min b_i$ 和 $\max b_i$ 求和，仍然会多出维度。我们换一种计算同一函数的方法。

扫描一个固定数组，维护状态 $c\in[0,n-1]$ 和累积代价 $A$。读入 $a_1$ 后初始化 $c=0,A=0$。随后读入 $a_i$ 时，先计算 $z=c+a_i-a_{i-1}-1$，再令 $A\leftarrow A+\max(0,z-n+1)$，$c\leftarrow\min(n-1,\max(0,z))$。

也就是把状态限制在 $[0,n-1]$ 内：碰到下界时截断，超过上界的部分计入答案。

在第一次上界截断之前，$c=b_i-\min_{j\le i}b_j$。一旦在第 $i$ 项发生上界截断，状态就变为 $n-1$；以后每读入一项，状态至多下降 $1$，而剩下只有 $n-i$ 项，所以之后再也不会碰到下界。此后每次产生的新代价，恰好对应 $b$ 的最大值继续增大。由此，最终累积代价正是 $F(a)$。

为了同时处理所有数组，将上述状态机展开成一个网格。

网格位置 $(r,x)$ 表示已经选择了前 $r$ 个坐标，目前扫描到坐标 $x$。在真正完成 $a_r$ 的选择后，状态仍属于 $[0,n-1]$；但为了把“大跨度转移”拆成单位步，允许水平扫描期间临时达到状态 $n$。

从 $(r,x)$ 向右走到 $(r,x+1)$，表示继续增大下一个坐标。状态更新为 $c\leftarrow\min(n,c+1)$；如果原来 $c=n$，此次移动产生 $1$ 的代价。

从 $(r,x)$ 向下走到 $(r+1,x)$，表示选择 $a_{r+1}=x$。这条边的权值为 $w_{r+1}(x)=[x\in S_{r+1}]$，状态更新为 $c\leftarrow\max(0,c-1)$。

在每个 $x\in S_1$ 对应的 $(1,x)$ 加入一个状态 $c=0$ 的起点；到达第 $n$ 行后立即结束，不再水平移动。每个合法数组恰好对应一条路径。两次选择之间，先进行若干次水平移动，再进行一次向下移动，正好实现前面的状态转移。

每个状态维护一对数 $(C,A)$：$C$ 是路径数，$A$ 是这些路径的累积代价之和。普通边直接传递这两个量，上界反射的水平边传递 $(C,A+C)$，边权为零时不传递。所有转移在模意义下进行。

这样已经得到一个 $O(n^2V)$ 时间、$O(nV)$ 滚动空间的算法。不过，这还没有利用不同 $c$ 状态之间的关系。

四叉分治与快速矩阵乘法

定义一个新的状态标签 $q=c-x+r$。

如果没有发生反射，水平移动让 $c,x$ 同时增加 $1$，竖直移动让 $c$ 减少 $1$、$r$ 增加 $1$，因此 $q$ 始终不变。只有两类边会改变它：下界反射把 $q$ 变成 $q+1$，上界反射把 $q$ 变成 $q-1$。

这意味着，除去两条反射边界，不同标签实际上都在运行同一个普通加权网格动态规划。

考虑左上角为 $(r_0,x_0)$、边长为 $s$ 的正方形网格块，令 $d=r_0-x_0$。块内可能发生下界反射的原标签形如 $q=r-x$，可能发生上界反射的原标签形如 $q=n+r-x$。把反射后的标签也包括进来，所有异常标签都包含在两个整数区间中：

$\mathcal E_B=[d-s+1,d+s]\ \cup\ [n+d-s,n+d+s-1]$。

这个集合至多包含 $4s$ 个标签。起点的标签为 $q=r-x$，也包含在其中。

因此，对于不属于 $\mathcal E_B$ 的标签，在整个块内都不会发生反射、不会产生新增代价，也不会出现源项。它们可以完全共用同一个线性变换。

先建立不带状态的块传递矩阵。 一个 $s\times s$ 的块有 $2s$ 个入口：上边界的 $s$ 个竖直入口和左边界的 $s$ 个水平入口；也有 $2s$ 个出口，分别位于下边界和右边界。忽略 $c$ 和反射，只保留原网格的边权，定义 $T_B$ 为从入口流量到出口流量的 $2s\times2s$ 传递矩阵。

这个矩阵不需要对每个入口分别跑一遍动态规划。把块四分为左上、右上、左下、右下四块，按左上、右上、左下、右下的拓扑顺序连接它们的传递矩阵。把父块的全部入口同时视为单位基向量，合成过程只需要常数次规模为 $O(s)$ 的矩阵乘法。因此，预处理满足 $P(s)=4P(s/2)+O(s^\omega)$，从而 $P(s)=O(s^\omega)$。

再批量计算真实的带状态动态规划。 设当前块需要处理的标签集合为 $Q$。将其分成普通标签 $G=Q\setminus\mathcal E_B$ 和异常标签 $R=Q\cap\mathcal E_B$。

对普通标签，将它们在块入口处的 $C,A$ 分别作为矩阵的列，一次乘上 $T_B$，就得到了它们的全部出口值。这些标签已经在当前层处理完毕，不再向子块递归。

只有异常标签 $R$ 才需要继续四分。四个子块仍然按拓扑顺序计算，前一个子块的出口成为后一个子块的入口。到达单个网格点时，直接执行原始的反射转移，并加入该点的源项。

核心递归可以写成下面的形式；N、W 分别表示上方、左方的入口，S、E 分别表示下方、右方的出口，每个入口都包含 $(C,A)$：

Solve(B, Q, N, W):
    如果 B 是单个网格点:
        合并 N 和 W
        加入本点的起点贡献
        执行水平、竖直转移，包括反射时的标签变化
        返回 S, E

    R = Q ∩ ExceptionalLabels(B)
    G = Q \ R

    将 N[G]、W[G] 的计数列和代价列拼成矩阵 X
    Y = FastMatrixMultiply(T[B], X)
    将 Y 拆回 S[G]、E[G]

    (S_NW, E_NW) = Solve(NW, R, N左半[R], W上半[R])
    (S_NE, E_NE) = Solve(NE, R, N右半[R], E_NW)
    (S_SW, E_SW) = Solve(SW, R, S_NW, W下半[R])
    (S_SE, E_SE) = Solve(SE, R, S_NE, E_SW)

    S[R] = 拼接(S_SW, S_SE)
    E[R] = 拼接(E_NE, E_SE)

    返回 S, E

这里有两个实现细节不能省略。第一，$Q$ 必须包含初值为零、但可能由反射产生的标签，不能只记录入口非零标签；异常集合同时包含反射前后的标签，正是为了保证递归对标签转移封闭。第二，源项只在所属单点加入一次，不计入普通传递矩阵。

真正降低复杂度的地方在于：标签数随着块的大小一起缩小。

对于边长为 $s$ 的非根块，传入的标签来自边长约为 $2s$ 的父块的异常集合，所以只有 $O(s)$ 个，而不是始终有 $O(n)$ 个。因此，该块的普通标签总共对应 $O(s)$ 列，批量传递只需要一次 $O(s^\omega)$ 的矩阵乘法。异常标签递归到四个子块，得到 $T(s)=4T(s/2)+O(s^\omega)=O(s^\omega)$。

如果每一层仍把全部 $n$ 个标签传给每个子块，这个降幂就不会成立。必须把普通标签在当前层一次性处理完，仅向下传递异常标签。

最后处理整个长方形网格。先将所有坐标同时减去全局最小坐标，使值域变为 $[0,V]$；这里只能平移，不能按不同坐标的排名离散化，因为实际距离参与答案。若某个集合为空，直接输出 $0$。若 $V\le n$，答案同样为 $0$：只要当前直径非零，每次操作都会让直径至少减少 $1$，而初始直径至多为 $n$。$n=1$ 也直接处理。

其余情况下 $V>n$，把网格沿水平方向分成 $O(V/n)$ 个边长为 $O(n)$ 的大块，从左到右处理。需要二次幂边长时，可以在网格上方补没有流量的虚行，并把起点保留在真实的第一行；真实路径不会因此多走竖直边。超出值域的边禁用。

在任一大块中，因为 $0\le c\le n$，而 $r-x$ 的变化范围只有 $O(n)$，所有可能出现的标签也只有 $O(n)$ 个，满足根递归的要求。前一个大块的右出口传给后一个大块的左入口；将所有大块下边界出口的 $A$ 相加，就是答案。

于是总复杂度为：

$$ \boxed{\text{时间 }O(K+Vn^{\omega-1}),\qquad \text{空间 }O(nV+n^2).} $$

空间界可以通过大块逐个处理、块内矩阵及时释放实现。需要某个子块的传递矩阵时允许重新构造；这不会增加渐近时间，因为各层的构造总量仍然是以 $s^\omega$ 为首项的几何级数。若直接缓存一棵大块四叉树的全部矩阵，则空间为 $O(nV+n^2\log n)$。

这里使用的是模域上的普通矩阵乘法，不是把 $\min/\max$ 半环乘法当作普通乘法。取 Strassen 的 $\omega=\log_2 7$，已经能够得到 $O(K+Vn^{1.807355\ldots})$；在 $V=\Theta(n)$ 时为 $O(n^{2.807355\ldots})$。([arXiv][1]) 使用已有的 $\omega< 2.371177$ 理论上界，还可写成 $O(K+Vn^{1.371177})$。([arXiv][2])