Archery Duel

Interview

Time limit1sMemory limit1024 MB

Summary

Two players alternately shoot a chained target or resign, and the task is to print the first player's score under optimal play.

Level: Medium5 of 10
Topics: Game theory, Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

Even in today's peaceful KSA class, students hold an archery duel. There are $N$ targets in total. One target is fixed at the top, and the rest hang one below another in a chain. Targets are numbered from $1$ to $N$ . Target $1$ is at the top, and target $i$ ( $1 < i \leq N$ ) hangs from target $i-1$ . The score of target $i$ is $A_i$ .

Two players take turns. On their turn, they may choose one of the following two actions.

Pick one target and shoot it down.
Resign.

When a target is hit, it is destroyed and its score is added to the score of the player who hit it. Targets hanging below the destroyed target fall. The scores of fallen targets that were not destroyed are added to the opponent's score. If a player resigns, the scores of all targets that are neither destroyed nor fallen are added to the opponent's score, and the game ends immediately. The game also ends when every target is destroyed or has fallen. Both students are excellent archers, so every chosen target is hit without fail, and each player makes only optimal choices to maximize their own score. Predict the result of the game.

Input

The first line contains the integer $N$ .

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$ , separated by spaces. These are the scores of the targets.

Output

Print the score that the first player takes.

Constraints

$1 \leq N \leq 2 \times 10^5$
$-10^9 \leq A_i \leq 10^9$

Examples3

Example 1
Input
```
3
1 10 100
```
Expected output
```
101
```
Example 2
Input
```
3
1 -10 -10
```
Expected output
```
1
```
Example 3
Input
```
2
-3 4
```
Expected output
```
1
```