温度校准

题目描述

在一个房间里，有 N 个位置，每个位置上有一个数字，表示这个位置的温度偏差，其中第 i 个位置的温度偏差为 Aᵢ，Aᵢ 可正可负。

房间里有一台空调，我们的目的是通过控制空调，消除所有温度偏差。

这台空调可以选择两个模式：制冷或制热，以及一个强度参数 x，x 至少为 1，至多为 N。

如果选择制冷模式，再设定 x 之后，空调开始运行，经过一小时后：

• 最后一个位置的温度下降 x 度
• 倒数第二个位置的温度下降 x-1 度
• 倒数第三个位置的温度下降 x-2 度
• 倒数第 x 个位置的温度会下降 1 度
• 其他位置保持温度不变。

如果选择制热模式，除了温度从下降改成上升之外与制冷模式没有区别。

空调可以以不同模式、不同强度运行任意多个小时。请问最少需要多少小时，才能让所有位置的温度偏差调成零。

输入格式

• 第一行：单个整数 N。
• 第二行：N 个整数 A₁,A₂,…,Aₙ。

输出格式

单个整数，表示最少需要的小时数。

数据范围

• 对于 30% 的数据，1 ≤ n ≤ 10
• 对于 60% 的数据，1 ≤ n ≤ 1000
• 对于 100% 的数据，1 ≤ n ≤ 1000000，-10⁹ ≤ Aᵢ ≤ 10⁹

样例输入 #1

2
-1 1

样例输出 #1

4

题目来源

改编自 USACO 2024 Jan, Balancing Bacteria

本题涉及的知识点从属于 GESP 五级，难度等级：⭐⭐⭐

测试点分布