两只白蚁正在吃一段旧木栅栏。这段栅栏由 $n$ 块高度可能不同的木板组成。白蚁们已经吃掉了一些木板，它们觉得应该让这顿饭变得更有趣些。它们决定玩一个游戏，轮流一块一块地吃木板。在一个回合中，白蚁只能选择吃掉与已经被吃掉的木板相邻的木板。

假设每只白蚁在选择木板时，都使得在整个游戏过程中它吃掉的所有木板的高度之和尽可能大，请计算它们各自将吃掉的木材总量。

输入格式

标准输入的第一行包含一个整数 $n$（$1 ≤ n ≤ 1\,000\,000$），表示栅栏中木板的数量。

第二行包含一个由 $n$ 个整数组成的序列 $l_{i}$（$0 ≤ l_{i} ≤ 1\,000\,000\,000$），描述了连续木板的高度。如果 $l_{i} = 0$，则表示相应的木板已经被吃掉了。第 $i$ 块木板（对于 $1 < i < n$）与第 $i-1$ 块和第 $i+1$ 块木板相邻。与第 1 块木板相邻的只有第 2 块木板，与第 $n$ 块木板相邻的只有第 $n-1$ 块木板。至少有一个 $l_{i}$ 等于 0。

输出格式

你应该在标准输出的第一行也是唯一一行输出两个整数。第一个整数应该是先手白蚁吃掉的木板高度之和，而第二个整数应该是它的对手吃掉的木材总量。

样例

输入 1

8
1 2 0 3 7 4 0 9

输出 1

17 9

说明 1

栅栏由 8 块木板组成，其中 2 块已经被吃掉了。第一只白蚁在它的第一个回合可以选择高度为 2、3、4 和 9 的木板。在最优游戏过程中，白蚁们在接下来的回合中将依次吃掉高度为 9、2、1、4、7 和 3 的木板。