← 返回题目列表

AtCoder · tessoku_book_ai

A35. 游戏 4

中文机器翻译题面 查看原题

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