← 返回题目列表

AtCoder · arc152_c

C. 枢轴

中文机器翻译题面 查看原题

分数: 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。