配点 : 1000 点
問題文
如下图 N 有一个金字塔,有几层,最底层从左到右包含整数。
写入 A_1,A_2,\dots,A_N 被写上了。另外,在最上面一层放置了 1 个棋子。
太郎君和次郎君将使用这个金字塔进行游戏。直到棋子到达最底层,每个玩家轮流进行以下操作之一(太郎君先手)。
- 将棋子向左下方移动 1 步。
- 将棋子向右下方移动 1 步。
游戏结束时棋子所在位置写的整数记为 分数 。当太郎君最大化分数、次郎君最小化分数时,分数是多少呢。

制約
- 所有输入均为整数
- 2 \le N \le 2000
- 1 \le A_i \le 100000
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 \dots A_N
出力
请以整数形式输出双方都尽力而为时的分数。
入力例 1
4 20 10 30 40
出力例 1
30