题目描述

一行N个正整数，两人轮流从中取数，每次只能取走最左端或者最右端的数，所取数的数值表示这个人这次的得分，所有数都取完时，每个人所行分数之和为这个人的最后得分，最后得分多的人获胜。如果两人得分相同，则规定首先取数的人获取。请编一个程序，作为首先取数的人，寻找一种必胜的策略和计算机玩这个游戏。

输入

第一行为一个正偶数N（2<=N<=1000），随后有N个不超过2000000的正整数。

输出

只有一行包含两个数（以一个空格分隔），第一个数是你的程序在这次游戏中的得分，第二个数是计算机的得分。

样例输入

6

4 7 2 9 5 2

样例输出

18 11