设 $f_i$ 为在 $i$ 号村庄建一个邮局的最小花费 $f_i=min_{j=1}^{i-1}\{f_j+\sum_{k=j+1}^{i}min(a_k-a_j,a_i-a_k)\}$

由于 $pos \le 10000$ 所以直接预处理每个位置对应左边第一个的村庄，若要从 $j$ 转移到 $i$ ，就取 $mid=\frac{a_j+a_i}{2}$ ，则 $\forall k\le pos_{mid}$ ，贡献是 $a_k-a_j$ ， $\forall k\gt pos_{mid}$ ，贡献是 $a_i-a_k$
于是我用了一个前缀和 $S_i$ 存前 $i$ 个村庄的距离和，即 $\sum{a_j}$ ，这样转移方程中右边的贡献就是
$[(S_{pos_{mid}}-S_j)-(pos_{mid}-j)a_j]+[(i-pos_{mid})a_i-(S_i-S_{pos_{mid}})]$

可以 $O(1)$ 计算，然后我又写了个决策单调性优化套上去

果断爆灵（

如果最后写 chk(r),write(dp[n]-r*p) ，不能过样例，但能拿30pts
如果写 chk(l),write(dp[n]-l*p) ，能过样例，但0pts
我怀疑是上述 $\text{DP}$ 方法的问题，但是想不到问题在哪里，求助

code