别让猴子掉下来

一座塔有 $H$ 层，每层都挂着一些猴子。楼层从下到上依次编号为 $1,2,\cdots,H$。最初，第 $i$ 层有 $a_i$ 只猴子。

Ishigami 和 Iino 轮流移除一个尚未被移除的楼层，Ishigami 先手。被移除楼层上的所有猴子都会移动到其下方尚未被移除的最高楼层。如果不存在这样的楼层，这些猴子就会掉到地面上，并全部归移除该楼层的玩家所有。之前回合中移动到该层的猴子也遵循相同规则。

没有猴子的楼层也可以被移除。所有楼层均被移除后，游戏结束。获得猴子较少的玩家获胜，数量相同则为平局。两人都会采取最优策略，使自己获得的猴子数量最少。求游戏结束时 Ishigami 和 Iino 各自获得的猴子数量。

输入格式如下：

$H$ $a_1\ a_2\ \cdots\ a_H$

依次输出 Ishigami 和 Iino 获得的猴子数量，用一个空格分隔。

• $1 \le H \le 1\,000\,000$.
• $0 \le a_i \le 10^9$ ().