Manju Game

AtCoder

IDagc026_f

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

5
20 100 10 1 10

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.

Input #2

6
4 5 1 1 4 5

Output #2

11 9

Input #3

5
1 10 100 10 1

Output #3

102 20

API Response (JSON)

{
  "problem": {
    "name": "Manju Game",
    "description": {
      "content": "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 alterna",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc026_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 alterna...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments