题目描述

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

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

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

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

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

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

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

输入格式

• 第一行：单个整数 $N$。
• 第二行：$N$ 个整数 $A_1,A_2,\dots,A_N$。

输出格式

2
-1 1

4

数据范围

• 对于 $30\%$ 的数据，$1\le n\le 10$
• 对于 $60\%$ 的数据，$1\le n\le 1,000$
• 对于 $100\%$ 的数据，$1\le n\le 1,000,000$，$\ -10^9\le a_i\le 10^9$。

来源

改编自 USACO 2024 Jan, Balancing Bacteria