题目描述

有一个包含 $N$ 项的数列 $a_1,a_2,\ldots,a_N$。你可以对这个数列进行任意次如下操作（也可以一次都不进行）：

• 从当前的数列中任选一项，其值记为 $s$。然后，对于所有 $1\leq i\leq N$，将 $a_i$ 替换为 $2s-a_i$。但注意，操作后数列中的所有项都不能为负数。

你希望通过适当的操作，使数列中的最大值尽可能小。请问，经过最优操作后，数列中的最大值最小是多少？

输入格式

输入通过标准输入给出，格式如下：

$N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

请输出一个整数，表示经过操作后数列中项的最小最大值。

样例 1

输入

3
1 3 6

输出

5

样例 2

输入

5
400 500 600 700 800

输出

400

说明/提示

限制条件

• $2\leq N\leq 2\times 10^5$
• $1\leq a_1<a_2<\ldots<a_N\leq 10^9$
• 输入的所有值均为整数

样例解释 1

如果以 $s=3$ 进行操作，数列变为 $(5,3,0)$。此时最大值为 $5$。在不产生负数的前提下，无法再进一步减小数列的最大值，因此答案为 $5$。

样例解释 2

可以选择 $s=400$ 进行一次操作，或者先以 $s=500$ 操作，再以 $s=300$ 操作等。

由 ChatGPT 4.1 翻译