当前没有测试数据。

G - 近似均衡化

得分：$550$ 分

问题描述

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

Takahashi 可以任意次数、任意顺序地执行以下两种操作之一：

• 选择一个整数 $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$ 满足以下条件：

• 对于任意的整数对 $(i,j)$，满足 $1$ 到 $N$ 之间的整数范围，有 $\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$ 满足问题描述中条件所需的最小操作次数。

3
2 7 6

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

你可以通过以下两个操作使 $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$。