题目描述

高桥和青木正在玩一个使用卡牌的游戏。

桌上有 $N$ 张卡牌排成一行。从左数第 $i$ 张卡牌上写着一个整数 $A_i$（$A_i$ 可以是负数）。

游戏规则如下：

• 高桥先手，高桥和青木轮流进行。
• 轮到某个玩家时，必须从当前行的左端或右端选择恰好 $1$ 张卡牌，并将其加入自己的手牌。被选择的卡牌从行中移除，剩余卡牌保持原有顺序。
• 当所有卡牌都被取走时，游戏结束。本题适合使用贪心策略，每次选择较大的卡牌。

每个玩家的得分是他们收集到的卡牌上整数之和。双方都采取最优策略，以最大化（自己的得分）−（对手的得分）。

当双方都采取最优策略时，分别求高桥的得分和青木的得分。

输入格式

第一行包含一个整数 $N$，表示卡牌的数量。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$，表示每张卡牌上写的整数，用空格分隔。

输出格式

输出一行，包含两个整数，依次为高桥的得分和青木的得分，用空格分隔。

4
1 2 3 4

6 4

5
3 -1 2 -5 4

-2 5

8
10 -3 7 2 -8 5 1 6

14 6

20
15 -7 23 -4 8 19 -12 6 3 -1 14 -9 7 25 -3 11 2 -18 20 5

77 27

1
-1000000000

-1000000000 0

数据范围

• $1 \le N \le 3000$
• $-10^9 \le A_i \le 10^9$
• 所有输入值均为整数

知识点与难度

本题涉及的知识点从属于 GESP六级（区间DP、博弈论），难度等级：中等。

来源

AtCoder AWC 0053D