/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 2000 点
問題文
N 個の箱が左右に一列に並んでいます。左から i 個目の箱にはまんじゅうが a_i 個入っています。 sugim君とsigma君はこの箱たちを使いゲームをします。 2人は交互に以下の操作を行います。先手はsugim君で，計 N 回操作を行ったらゲームを終了します。
- 相手が最後にコマを入れた箱に隣り合う箱で，まだコマが入っていないものを選び，コマを入れる。条件を満たす箱が複数ある場合，好きな箱を 1 つ選べる。
- 上記の条件を満たす箱が存在しない場合，及びsugim君の最初の操作では，まだコマが入っていない箱をどれか好きに 1 つ選び，コマを入れる。
最終的に 2 人は，自分がコマを入れた箱のまんじゅうたちを得ることが出来ます。 2 人は十分に頭がよく，またまんじゅうが大好きなので，自分が得られるまんじゅうの個数を最大化するために最適に行動を行います。
2 人が得られるまんじゅうの個数はいくつになるかを求めて下さい。
制約
- 2 \leq N \leq 300,000
- 1 \leq a_i \leq 1000
- 入力される値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
出力
sugim君が得られるまんじゅうの個数と，sigma君が得られるまんじゅうの個数を，この順で空白区切りで出力せよ。
入力例 1
5 20 100 10 1 10
出力例 1
120 21
二人が最適に行動した場合，以下のようにゲームは進んでいきます。
- sugim君は最初に左から 2 番目の箱にコマを入れる必要があります。
- 次にsigma君は左端の箱にコマを入れる必要があります。
- 次にsugim君は左から 3 番目，もしくは 5 番目の箱にコマを入れます。
- 次にsigma君は左から 4 番目の箱にコマを入れます。
- 最後にsugim君は残った箱にコマを入れます。
入力例 2
6 4 5 1 1 4 5
出力例 2
11 9
入力例 3
5 1 10 100 10 1
出力例 3
102 20
Score : 2000 points
Problem Statement
There are N boxes arranged in a row from left to right. The i-th box from the left contains a_i manju (buns stuffed with bean paste). Sugim and Sigma play a game using these boxes. They alternately perform the following operation. Sugim goes first, and the game ends when a total of N operations are performed.
- Choose a box that still does not contain a piece and is adjacent to the box chosen in the other player's last operation, then put a piece in that box. If there are multiple such boxes, any of them can be chosen.
- If there is no box that satisfies the condition above, or this is Sugim's first operation, choose any one box that still does not contain a piece, then put a piece in that box.
At the end of the game, each player can have the manju in the boxes in which he put his pieces. They love manju, and each of them is wise enough to perform the optimal moves in order to have the maximum number of manju at the end of the game.
Find the number of manju that each player will have at the end of the game.
Constraints
- 2 \leq N \leq 300 000
- 1 \leq a_i \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Output
Print the numbers of Sugim's manju and Sigma's manju at the end of the game, in this order, with a space in between.
Sample Input 1
5 20 100 10 1 10
Sample Output 1
120 21
If the two performs the optimal moves, the game proceeds as follows:
- First, Sugim has to put his piece in the second box from the left.
- Then, Sigma has to put his piece in the leftmost box.
- Then, Sugim puts his piece in the third or fifth box.
- Then, Sigma puts his piece in the fourth box.
- Finally, Sugim puts his piece in the remaining box.
Sample Input 2
6 4 5 1 1 4 5
Sample Output 2
11 9
Sample Input 3
5 1 10 100 10 1
Sample Output 3
102 20