サルを落とさないで

$H$ 階建ての塔の各階にサルがぶら下がっている。階には下から順に $1,2,\cdots,H$ の番号が付いており、最初、階 $i$ には $a_i$ 匹のサルがいる。

Ishigami と Iino は交互に、残っている階を $1$ つ取り除く。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$ ().