题目描述

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

高桥可以任意次数（可能为零次）以任意顺序执行以下两种操作之一：

• 选择一个整数 $i$，满足 $1\\leq i\\leq N-1$ ，将 $A_i$ 减 $1$ 并将 $A_{i+1}$ 加 $1$。
• 选择一个整数 $i$，满足 $1\\leq i\\leq N-1$ ，将 $A_i$ 加 $1$ 并将 $A_{i+1}$ 减 $1$。

找出使序列 $A$ 满足以下条件所需的最小操作次数：

• 对于介于 $1$ 和 $N$ 之间的任意整数对 $(i,j)$，都满足 $\\lvert A_i-A_j\\rvert\\leq 1$。

约束条件

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

输入

输入数据从标准输入中获取，格式如下：

$N$ $A_1$ $A_2$ $\\ldots$ $A_N$

输出

打印一行，其中包含使序列 $A$ 满足问题描述中条件所需的最小操作次数。

示例输入 1

3
2 7 6

示例输出 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

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

示例输入 3

5
1 1 1 1 -7

示例输出 3

13

通过适当执行操作，您可以进行 $13$ 次操作来使 $A=(0,0,-1,-1,-1)$，从而满足问题描述中的条件。不可能用 $12$ 次或更少的操作满足条件，因此打印 $13$。