分数: 600 点
问题陈述
我们有一系列 N 条款: a_1,a_2,\ldots,a_N。 您可以对该序列执行以下操作任意次数(可能为零)。
- 在该点选择序列的一项,然后让 s 是它的值。 那么,对于每一个 1\leq i\leq N,替换 a_i 与 2s-a_i。 然而,该操作不能以产生负值项的方式执行。
您希望使序列项中的最大值尽可能小。 在针对此目标执行最佳操作序列后,该值会是多少?
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq a_1 < a_2 < \ldots < a_N \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N a_1 a_2 \ldots a_N
输出
打印答案。
示例输入 1
3 1 3 6
示例输出 1
5
如果您执行操作 s=3,序列变为 (5,3,0)。这里最大的价值就是 5。 在可能不存在负值项的情况下,序列项中的最大值无法变小,所以应该打印 5.
示例输入 2
5 400 500 600 700 800
示例输出 2
400
要获得此结果,请使用以下命令执行一次操作 s=400,或执行它 s=500 然后用 例如, s=300。