[ABC307G] Approximate Equalization

给定一个长度为 $n$ 的序列 $a$，你可以： + 选择 $1\leq i<n$，令 $a_i$ 减去 $1$、$a_{i+1}$ 加上 $1$。 + 选择 $1\leq i<n$，令 $a_i$ 加上 $1$、$a_{i+1}$ 减去 $1$。 你要让 $a$ 中任意两个数相差不超过 $1$，输出最少步数。

[problemUrl]: https://atcoder.jp/contests/abc307/tasks/abc307_g 長さ $ N $ の整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 高橋君は次の $ 2 $ 種類の操作のうち $ 1 $ つを選んで行う事を、何回でも ($ 0 $ 回でも良い) 繰り返し行う事ができます。 - $ 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 $ 以上 $ N $ 以下の整数の組 $ (i,j) $ に対して、$ \lvert\ A_i-A_j\rvert\leq\ 1 $ が成り立つ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

数列 $ A $ が問題文の条件をみたすようにするために必要な操作の回数の最小値を一行に出力せよ。

3
2 7 6

4

3
-2 -5 -2

2

5
1 1 1 1 -7

13

### 制約 - $ 2\ \leq\ N\ \leq\ 5000 $ - $ \lvert\ A_i\ \rvert\ \leq\ 10^9 $ - 入力はすべて整数 ### Sample Explanation 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 $ を出力します。 ### Sample Explanation 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 $ を出力します。 ### Sample Explanation 3 うまく操作することで、$ 13 $ 回の操作の後で、 $ A=(0,0,-1,-1,-1) $ にでき、これは問題文の条件をみたします。 $ 12 $ 回以下の操作で条件をみたすようにすることはできないため、$ 13 $ を出力します。