PA2010 Termites

时间限制:10s      空间限制:128MB

题目描述

有两个玩家,会去挑选一些数字,每次只能选至少与一个0相邻的数字(不能选0),拿完一个数字后这个数字  会变成0。
两个玩家都采取最优策略,使自己拿到的数字的和最大,问最后两位玩家的得分。
数字个数< 1000000,保证初始时至少有一个0。


输入格式


输出格式


样例输入

8
1 2 0 3 7 4 0 9


样例输出

17 9

提示


Explanation of the example: The fence consisted of 8 planks, out of which 2 have already been eaten. The first termite in his first turn can choose between planks of heights 2, 3, 4 and 9. During the optimal game, in the consecutive turns, termites will eat planks of heights 9, 2, 1, 4, 7 and 3.


题目来源

没有写明来源