都--两端取数游戏

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

才神,作为上一次差点把本战五渣的题AK的选手,本渣还是很害怕的,所以这次特地为才神准备来了一道题。
有两个好基友Alice和Bob,和一个含有n个数的序列,两人每次从序列两端任取一个数,取数后该数字被去掉并累加到本玩家的得分中,当数取尽时,游戏结束。以最终得分多者为胜。Alice先手。你可以认为两个人都足够聪明,每次选取都保证自己的总得分尽可能的多,对方的尽可能的少。

Input

多组输入。每组数据输入一个数n(1 <= n && n <= 100)。接下来的一行有n个数,表示这个序列。序列中的每个元素的取值范围为[1,200]。

Output

对于每组数据,输出两个数a,b,分别代表Alice和Bob的最终得分。

Sample Input

6
4 7 2 9 5 2
3
100 110 100

Sample Output

18 11
200 110

Hint

对于第一组样例,取的次序为 2 4 7 5 9 2 ,所以Alice得分为 2 + 7 + 9 = 18,Bob得分为 4+5+2 = 11。

Source