ARC126E

断言：令 $D = \sum \limits_{i=1}^n \sum \limits_{j=1}^n |a_i-a_j|$，即每个点到其它所有点的距离之和，则答案为 $\frac{1}{4}D$。

证明：我们可以把每次操作拆成若干次操作，使得每次操作过后，不会有一对 $p,q$ 满足在操作前有 $a_p<a_q$，在操作后有 $a_p>a_q$。

当我们操作下标 $i,j(a_i<a_j)$ 相互靠近 $x$ 距离时，由于只有 $i,j$ 被改了，所以受到影响的只有所有点与 $i,j$ 之间的距离。

对于 $i$ 左边的数 $l$，即 $a_l<a_i$，贡献为 $a_i-a_l+a_j-a_l$。由于 $a_i \leftarrow a_i+x$，$a_j \leftarrow a_j-x$，所以 $l$ 的贡献不会改变。

对于中间的数 $m$，即 $a_i<a_m<a_j$，贡献为 $a_m-a_i+a_j-a_m=a_j-a_i$，变化后 $m$ 的贡献会减少 $2x$。

对于右边的数 $r$，即 $a_j<a_r$，贡献为 $a_r-a_i+a_r-a_j$，变化后 $r$ 的贡献不变。

而 $i,j$ 本身的贡献会减少 $4x$。

所以每次贡献至少减少 $4x$，并且当且仅当中间没有数，即 $i,j$ 相邻时取等。

于是得证。