配点 : $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$

出力

答えを整数として出力せよ。

3
0 6 10

5

$5$ 秒間のパーティーの間、各人は以下のように移動するとよいです。

• 人 $1$ : 常に正の向きに速さ $1$ で移動する
• 人 $2$ : 最初の $2$ 秒間は正の向きに速さ $1$ で移動し、残りの $3$ 秒間は負の向きに速さ $1$ で移動する
• 人 $3$ : 常に負の向きに速さ $1$ で移動する

各人がこのように移動した場合、開始からちょうど $2$ 秒後に人 $2$ と人 $3$ が同じ座標にいます。また、パーティーの終了時に人 $1$ と人 $2$ が同じ座標にいます。 よって、$k = 5$ の場合、条件を全て満たすことができます。これより小さい $k$ では条件を全て満たすような移動の仕方は存在しません。

5
0 2 4 6 8

3

$3$ 秒間のパーティーの間、各人は例えば以下のように移動するとよいです。

• 人 $1$ : 常に正の向きに速さ $1$ で移動する
• 人 $2$ : 最初の $2$ 秒間は正の向きに速さ $1$ で移動し、残りの $1$ 秒間は負の向きに速さ $1$ で移動する
• 人 $3$ : 常に移動しない
• 人 $4$ : 最初の $2$ 秒間は負の向きに速さ $1$ で移動し、残りの $1$ 秒間は正の向きに速さ $1$ で移動する
• 人 $5$ : 常に負の向きに速さ $1$ で移動する

10
0 2 4 6 8 92 94 96 98 100

44