配点 : $600$ 点

問題文

$N$ 項からなる数列 $a_1,a_2,\ldots,a_N$ があります。 あなたはこれから、この数列に以下の操作を好きな回数行うことができます。（$1$ 回も行わなくてもよいです。）

• その時点の数列から項を $1$ つ選び、その値を $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$

出力

答えを整数で出力せよ。

3
1 3 6

5

$s=3$ として操作を行うと、数列は $(5,3,0)$ になります。このとき最大値は $5$ です。 数列に負の項が生じてはいけないという条件の下で、これ以上数列の項の最大値を小さくすることはできませんので、$5$ と答えてください。

5
400 500 600 700 800

400

$s=400$ として操作を一度行うほか、$s=500$ として操作を行った後、$s=300$ としてもう一度操作を行うなどの方法が考えられます。