样例下载

题目描述

Alice 和 Bob 正在玩数字游戏。

有 $N$ ( $N$ 是偶数) 个整数 $X_i$ 排成一排。

Alice 和 Bob 依次交替进行游戏。Alice 先手。

每次 Alice 可以任意选择两个相邻的整数，用它们的和替代原先的两个整数。

每次 Bob 可以任意选择两端中的某一端的数取走。

当原先的一排整数只剩下一个整数时，游戏结束。

此时 Alice 得到剩下的这一个整数作为他的游戏得分。而 Bob 得到他取走的所有整数的和作为他的游戏得分。

两个人都足够聪明。问：Alice 和 Bob 最后能得到的最大得分分别是多少？

多组数据。

输入格式

第一行：一个整数 $T$，表示数据组数。

对于每组数据：

• 第一行：一个整数 $N$。
• 第二行：$N$ 个整数 $X_i$

数据保证所有组数据的 $\sum N ≤ 10^6$。

输出格式

共 T 行，每组数据的答案占一行，包含两个整数，分别表示 Alice 和 Bob 能得到的最大得分。

输入数据

3
2
1 2
4
1 2 3 4
4
1 3 4 2

输出数据

3 0
6 4
8 2

数据范围

100% 的数据：$1 ≤ T ≤ 10, 2 ≤ N ≤ 5×10^5$，数据保证 $N$ 是偶数。$1 ≤ X_i ≤ 10^9$。其中：

• 10% 的数据：所有 $X_i$ 相等。
• 10% 的数据：$N ≤ 10$。
• 30% 的数据：$N ≤ 5000$。