近似等化

题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。

高桥君可以任意次数(可能为 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

可以用如下 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$。

3
-2 -5 -2

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$。

5
1 1 1 1 -7

13

通过适当执行操作,用 $13$ 次操作可以使 $A=(0,0,-1,-1,-1)$,满足题目描述的条件。

不可能用 $12$ 次或更少的操作满足条件,因此输出 $13$。

数据范围

• $2 \le N \le 5000$
• $\lvert A_i\rvert \le 10^9$
• 输入中的所有值均为整数