/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
人 1 から人 N までの N 人の人が数直線上に並んでいます。人 i は今数直線上の座標 A_i にいます。
ここで、A_1 < A_2 < A_3 < \dots < A_N であり、A_i は全て偶数です。
今から k 秒間のパーティーを開きます。
パーティー中、各人は毎秒 1 以下の速さで数直線上を自由に動くことができます。(速さが毎秒 1 以下であれば負の向きに動くこともできます。)
参加者の希望により、1 \le i \lt N を満たす全ての整数 i について以下の条件を満たす必要があります。
- 人 i と人 i + 1 が同じ座標にいる瞬間が、パーティー中 (終了の瞬間も含む) に少なくとも 1 回存在する
各人が最適に行動すると条件を全て満たすことができるような最小の k を求めてください。
この問題の制約下で答えが整数になることが証明できます。
制約
- 2 \le N \le 2 \times 10^5
- 0 \le A_i \le 10^9
- A_1 < A_2 < A_3 < \dots < A_N
- A_i は偶数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 A_3 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
3 0 6 10
出力例 1
5
5 秒間のパーティーの間、各人は以下のように移動するとよいです。
- 人 1 : 常に正の向きに速さ 1 で移動する
- 人 2 : 最初の 2 秒間は正の向きに速さ 1 で移動し、残りの 3 秒間は負の向きに速さ 1 で移動する
- 人 3 : 常に負の向きに速さ 1 で移動する
各人がこのように移動した場合、開始からちょうど 2 秒後に人 2 と人 3 が同じ座標にいます。また、パーティーの終了時に人 1 と人 2 が同じ座標にいます。
よって、k = 5 の場合、条件を全て満たすことができます。これより小さい k では条件を全て満たすような移動の仕方は存在しません。
入力例 2
5 0 2 4 6 8
出力例 2
3
3 秒間のパーティーの間、各人は例えば以下のように移動するとよいです。
- 人 1 : 常に正の向きに速さ 1 で移動する
- 人 2 : 最初の 2 秒間は正の向きに速さ 1 で移動し、残りの 1 秒間は負の向きに速さ 1 で移動する
- 人 3 : 常に移動しない
- 人 4 : 最初の 2 秒間は負の向きに速さ 1 で移動し、残りの 1 秒間は正の向きに速さ 1 で移動する
- 人 5 : 常に負の向きに速さ 1 で移動する
入力例 3
10 0 2 4 6 8 92 94 96 98 100
出力例 3
44
Score : 700 points
Problem Statement
There are N people, Person 1 through Person N, standing on a number line. Person i is now at coordinate A_i on the number line.
Here, A_1 < A_2 < A_3 < \dots < A_N and all A_i are even numbers.
We will now hold a party for k seconds.
During the party, each person can freely move on the number line at a speed of at most 1 per second. (It is also allowed to move in the negative direction within the speed limit.)
The people request that the following condition be satisfied for every integer i such that 1 \le i \lt N:
- there is at least one moment during the party (including the moment it ends) when Person i and Person i + 1 are at the same coordinate.
Find the minimum k for which there is a strategy that the people can take to satisfy all the conditions.
We can prove that the answer is an integer under the Constraints of this problem.
Constraints
- 2 \le N \le 2 \times 10^5
- 0 \le A_i \le 10^9
- A_1 < A_2 < A_3 < \dots < A_N
- A_i is an even number.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 A_3 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
3 0 6 10
Sample Output 1
5
During the party lasting 5 seconds, each person should move as follows:
- Person 1: always moves in the positive direction at a speed of 1.
- Person 2: moves in the positive direction at a speed of 1 during the first 2 seconds, then in the negative direction at a speed of 1 during the remaining 3 seconds.
- Person 3: always moves in the negative direction at a speed of 1.
If they move in this way, Person 2 and Person 3 will be at the same coordinate exactly 2 seconds after the beginning, and Person 1 and Person 2 will be at the same coordinate at the end of the party.
Thus, they can satisfy all the conditions for k = 5. For smaller k, there is no strategy to satisfy all of them.
Sample Input 2
5 0 2 4 6 8
Sample Output 2
3
During the party lasting 3 seconds, each person should, for example, move as follows:
- Person 1: always moves in the positive direction at a speed of 1.
- Person 2: moves in the positive direction at a speed of 1 during the first 2 seconds, then in the negative direction at a speed of 1 during the remaining 1 second.
- Person 3: does not move at all.
- Person 4: moves in the negative direction at a speed of 1 during the first 2 seconds, then in the positive direction at a speed of 1 during the remaining 1 second.
- Person 5: always moves in the negative direction at a speed of 1.
Sample Input 3
10 0 2 4 6 8 92 94 96 98 100
Sample Output 3
44