题目描述

我们有一个包含 $N$ 个元素的序列：$a_1,a_2,\ldots,a_N$。你可以对这个序列进行任意次数的以下操作（可能为零次）。

• 选择序列中的某一项，令 $s$ 为它的值。然后，对于每个 $1\leq i\leq N$，用 $2s-a_i$ 替换 $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$ 进行一次操作，等等。