题目描述

夜市里摆着一排 $N$ 个蛋糕，大小依次为 $a_1,a_2,\dots,a_N$（$N$ 为偶数）。两位朋友阿明和小雅约好用游戏来分蛋糕，轮流操作，且阿明先手：

• 轮到阿明：选一对相邻蛋糕，把它们合成一个（新大小为两者之和）；
• 轮到小雅：从最左或最右拿走一个蛋糕，先藏起来。

当桌上只剩一个蛋糕时，阿明吃掉这最后一个；小雅吃掉她之前藏起来的所有蛋糕。两人都想让自己吃到的蛋糕总量尽可能多。问在最优策略下，两人各能吃到多少蛋糕？

输入格式

第一行一个整数 $T$，表示测试用例个数。 每个测试用例： 第一行一个整数 $N$。 第二行 $N$ 个整数 $a_1,a_2,\dots,a_N$。

输出格式

对每个测试用例输出一行两个整数，表示阿明和小雅在最优策略下各自吃到的蛋糕总量（先输出阿明，再输出小雅）。

输入输出样例 #1

输入 #1

2
4
40 30 20 10
4
10 20 30 40

输出 #1

60 40
60 40

样例解释

第一组：阿明先把中间两块合成为 $[40,50,10]$；小雅拿走最左边，剩 $[50,10]$；阿明再合成最后两块。最终阿明吃 $30+20+10=60$，小雅吃 $40$。第二组为反转，答案相同。

数据范围

对于30%的数据：$1 \le T \le 10$；$2 \le N \le 5000$；$1 \le a_i \le 10^9$；$\sum N \le 10^5$；$N$ 为偶数

对于100%的数据：$1 \le T \le 10$；$2 \le N \le 5\times 10^5$；$1 \le a_i \le 10^9$；$\sum N \le 10^6$；$N$ 为偶数