No.484 収穫

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 34
作問者 : ei1333ei1333 / テスター : tanzakutanzaku

8 ProblemId : 1428 / 出題時の順位表

問題文

$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 行に, タヌキくんがすべてのセルの木の実の収穫を終える最短時刻を出力してください。

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

サンプル

サンプル1
入力
3
0 1 1
出力
2

時刻 $0$ にセル $1$, 時刻 $1$ にセル $2, 3$ の木の実が実ります。

例えば最初の位置としてセル $1$ を選択します。
時刻 $0$ にセル $1$ の木の実を収穫します。
時刻 $1$ にセル $2$ に移動し, セル $2$ の木の実を収穫します。
時刻 $2$ にセル $3$ に移動し, セル $3$ の木の実を収穫します。

これが最短時刻なので $2$ を出力します。

サンプル2
入力
3
5 1 4
出力
6

例えば, 最初の位置としてセル $2$ を選択します。
時刻 $0$ はそのままです。
時刻 $1$ にセル $2$ の木の実を収穫します。
時刻 $2$ にセル $3$ に移動します。
時刻 $3$ はそのままです。
時刻 $4$ にセル $3$ の木の実をを収穫します。
時刻 $5$ にセル $2$ に移動します。
時刻 $6$ にセル $1$ に移動し, セル $1$ の木の実を収穫します。

これが最短時刻なので $6$ を出力します。

サンプル3
入力
3
1333 1000000000 1333
出力
1000000000

セル $2$ の木の実が実るまで長い時間を待つ必要があります。

提出ページヘ