問題文

下図のような N 段のピラミッドがあり、最下段には左から順に整数 A_1,A_2,\dots,A_N が書かれています。また、最上段には 1 つのコマが置かれています。
太郎君と次郎君は、このピラミッドを使ってゲームをします。コマが最下段に到達するまで、各プレイヤーは交互に以下のいずれかの操作を行います（太郎君が先手です）。

• コマを左下方向に 1 つ移動させる。
• コマを右下方向に 1 つ移動させる。

ゲーム終了時のコマの位置に書かれた整数を スコア とします。太郎君はスコアを最大化し、次郎君はスコアを最小化するとき、スコアはいくつになりますか。

制約

• 入力は全て整数
• 2 \le N \le 2000
• 1 \le A_i \le 100000

入力例 1

4
20 10 30 40

出力例 1

30