分数: 300 分
问题陈述
高桥和青木正在互相玩抽牌游戏。
有 N 卡片放在桌子上。每张卡片的编号为 1 to N和卡 i 有一个正整数 A_i 。
游戏按照以下规则进行:
- 两名玩家的开局得分均为 从桌上剩余的牌中选择 0.
- 高桥先行,高桥和青木轮流轮流。
- 在轮到他们时,玩家必须准确选择 从当前行的左端或右端选择 1 牌并拿走它(不允许传递)。所拿的牌将从表中移除,并且该牌上写的整数将添加到该玩家的分数中。
- 当所有牌都被拿走后,游戏结束。
根据上述规则,高桥将采取 \lceil N/2 \rceil 卡和青木将采取 \lfloor N/2 \rfloor 卡。
高桥以最佳方式发挥最大化(高桥的分数) - (青木的得分),并且青木发挥最优以最小化(高桥的得分) - (青木的分数)。查找(高桥的分数) - (青木的得分)当两名球员都发挥最佳状态时。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 所有输入均为整数
输入
N A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表卡片数量。 卡上写着
- 第二行包含 N 整数 A_i (i = 1, 2, \ldots, N) 写在卡片上 i,用空格分隔。
输出
在单行中以整数形式输出(高桥分数)的值 - (青木的得分)当两名球员都发挥最佳状态时。
示例输入 1
3 10 20 30
示例输出 1
20
示例输入 2
5 1 2 3 4 5
示例输出 2
3
示例输入 3
8 100 50 80 120 90 30 70 60
示例输出 3
60