题目描述

有一个长度为 $n$ 的数列 $a$，两名玩家轮流行动，每次可以选择一个与 $0$ 相邻的数字，得到数字大小的得分，并将它变为 $0$。求如果两个人都采取最优策略，两个人的得分。

输入格式

第一行一个整数 $n$，意义如题面。

接下来一行 $n$ 个整数，表示这个数列。

输出格式

一行两个整数，表示两个人都采取最优策略的答案。

8
1 2 0 3 7 4 0 9

17 9

提示

数据规模与约定

对于全部的测试点，保证 $1\leq n\leq 10^6$，且对于任何一个 $a$ 中的元素 $x$，都保证 $0\leq x\leq 10^6$ 且至少存在一个 $0$。