AT_abc307_g [ABC307G] Approximate Equalization

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。 高桥君可以无限次（也可以不进行）重复以下两种操作中的任意一种： - 选择满足 $1\leq i\leq N-1$ 的整数 $i$，将 $A_i$ 减 $1$，将 $A_{i+1}$ 加 $1$。 - 选择满足 $1\leq i\leq N-1$ 的整数 $i$，将 $A_i$ 加 $1$，将 $A_{i+1}$ 减 $1$。 请你求出，为了使数列 $A$ 满足以下条件，所需操作次数的最小值： - 对于任意 $1\leq i,j\leq N$，都有 $|A_i-A_j|\leq 1$。

输入以如下格式从标准输入读入： > $N$ $A_1$ $A_2$ $\ldots$ $A_N$

请输出使数列 $A$ 满足题目条件所需的最小操作次数。

## 限制条件 - $2\leq N\leq 5000$ - $|A_i|\leq 10^9$ - 输入均为整数 ## 样例解释 1 可以通过如下方式在 $4$ 次操作后使 $A$ 满足条件： - 选择 $i=1$，将 $A_1$ 加 $1$，$A_2$ 减 $1$，此时 $A=(3,6,6)$。 - 选择 $i=1$，将 $A_1$ 加 $1$，$A_2$ 减 $1$，此时 $A=(4,5,6)$。 - 选择 $i=2$，将 $A_2$ 加 $1$，$A_3$ 减 $1$，此时 $A=(4,6,5)$。 - 选择 $i=1$，将 $A_1$ 加 $1$，$A_2$ 减 $1$，此时 $A=(5,5,5)$。 此时操作次数最小，因此输出 $4$。 ## 样例解释 2 可以通过如下方式在 $2$ 次操作后使 $A$ 满足条件： - 选择 $i=1$，将 $A_1$ 减 $1$，$A_2$ 加 $1$，此时 $A=(-3,-4,-2)$。 - 选择 $i=2$，将 $A_2$ 加 $1$，$A_3$ 减 $1$，此时 $A=(-3,-3,-3)$。 此时操作次数最小，因此输出 $2$。 ## 样例解释 3 通过合理操作，在 $13$ 次操作后可以得到 $A=(0,0,-1,-1,-1)$，满足题目条件。用 $12$ 次或更少的操作无法满足条件，因此输出 $13$。 由 ChatGPT 4.1 翻译