AT_agc026_f [AGC026F] Manju Game

$ N $ 個の箱が左右に一列に並んでいます。左から $ i $ 個目の箱にはまんじゅうが $ a_i $ 個入っています。 sugim君とsigma君はこの箱たちを使いゲームをします。 2人は交互に以下の操作を行います。先手はsugim君で，計 $ N $ 回操作を行ったらゲームを終了します。 - 相手が**最後に**コマを入れた箱に隣り合う箱で，まだコマが入っていないものを選び，コマを入れる。条件を満たす箱が複数ある場合，好きな箱を $ 1 $ つ選べる。 - 上記の条件を満たす箱が存在しない場合，及びsugim君の最初の操作では，まだコマが入っていない箱をどれか好きに $ 1 $ つ選び，コマを入れる。 最終的に $ 2 $ 人は，自分がコマを入れた箱のまんじゅうたちを得ることが出来ます。 $ 2 $ 人は十分に頭がよく，またまんじゅうが大好きなので，自分が得られるまんじゅうの個数を最大化するために最適に行動を行います。 $ 2 $ 人が得られるまんじゅうの個数はいくつになるかを求めて下さい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $

sugim君が得られるまんじゅうの個数と，sigma君が得られるまんじゅうの個数を，この順で空白区切りで出力せよ。

### Sample Explanation 1 二人が最適に行動した場合，以下のようにゲームは進んでいきます。 - sugim君は最初に左から $ 2 $ 番目の箱にコマを入れる必要があります。 - 次にsigma君は左端の箱にコマを入れる必要があります。 - 次にsugim君は左から $ 3 $ 番目，もしくは $ 5 $ 番目の箱にコマを入れます。 - 次にsigma君は左から $ 4 $ 番目の箱にコマを入れます。 - 最後にsugim君は残った箱にコマを入れます。 ### Constraints - $ 2 \leq N \leq 300,000 $ - $ 1 \leq a_i \leq 1000 $ - 入力される値は全て整数である