/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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
出力
答えを整数で出力せよ。
入力例 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 としてもう一度操作を行うなどの方法が考えられます。
Score : 600 points
Problem Statement
We have a sequence of N terms: a_1,a_2,\ldots,a_N. You can perform the following operation on this sequence any number of times (possibly zero).
- Choose a term of the sequence at that point, and let s be its value. Then, for every 1\leq i\leq N, replace a_i with 2s-a_i. However, this operation may not be performed in a way that produces a term with a negative value.
You want to make the greatest value among the terms of the sequence as small as possible. What will this value be after an optimal sequence of operations for this objective?
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq a_1 < a_2 < \ldots < a_N \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N a_1 a_2 \ldots a_N
Output
Print the answer.
Sample Input 1
3 1 3 6
Sample Output 1
5
If you perform the operation with s=3, the sequence becomes (5,3,0). The greatest value here is 5. Under the condition that there may not be a term with a negative value, the greatest value among the terms of the sequence cannot be made smaller, so you should print 5.
Sample Input 2
5 400 500 600 700 800
Sample Output 2
400
To obtain this result, perform the operation once with s=400, or perform it with s=500 and then with s=300, for instance.