問題文

$N$ 個のセルが横に並んでいて, 左のセルから順に $1, 2, \dots, N$ の番号が振られています。

それぞれのセルには実がなる木が $1$ 本ずつ植えられていて, セル $i$ の木の実は時刻 $A_i$ に実ることが分かっています。 一度実った実は, 収穫するまでなくなることはありません。

タヌキくんは時刻 $0$ から任意のセルより行動を開始できます。 タヌキくんは急な動きが苦手なので, 単位時間に隣接するセルに移動するか, そのセルに留まるかのどちらかしかできません。 任意のタイミングで, 自分のいるセルの木に実った実を収穫することができます。 タヌキくんは収穫のプロなので, 収穫するためにかかる時間は無視できます。

タヌキくんはお腹をすかせているので, すべてのセルの木の実を出来るだけ早く収穫したいです。 そこで, すべてのセルの木の実の収穫を終える最短時刻を求めてください。

入力

$N$
$A_{1}\ A_{2}\ \dots\ A_{N}$

$1$ 行目にセルの数 $N(1 \le N \le 2\ 000)$ が与えられます。

$2$ 行目に $N$ 個の値が半角空白区切りで与えられます。 このうち $i(1 \le i \le N)$ 番目の値は, セル $i$ の木の実が時刻 $A_i(0 \le A_i \le 10^9)$ に実ることを意味します。

出力

1 行に, タヌキくんがすべてのセルの木の実の収穫を終える最短時刻を出力してください。

最後に改行してください。

サンプル

3
0 1 1

2

3
5 1 4

6

3
1333 1000000000 1333

1000000000