题目描述
一行N个正整数,两人轮流从中取数,每次只能取走最左端或者最右端的数,所取数的数值表示这个人这次的得分,所有数都取完时,每个人所行分数之和为这个人的最后得分,最后得分多的人获胜。如果两人得分相同,则规定首先取数的人获取。请编一个程序,作为首先取数的人,寻找一种必胜的策略和计算机玩这个游戏。
输入
第一行为一个正偶数N(2<=N<=1000),随后有N个不超过2000000的正整数。
输出
只有一行包含两个数(以一个空格分隔),第一个数是你的程序在这次游戏中的得分,第二个数是计算机的得分。
样例输入
6
4 7 2 9 5 2
样例输出
18 11