CF731E.Funny Game

Once upon a time Petya and Gena gathered after another programming competition and decided to play some game. As they consider most modern games to be boring, they always try to invent their own games. They have only stickers and markers, but that won't stop them.

The game they came up with has the following rules. Initially, there are n stickers on the wall arranged in a row. Each sticker has some number written on it. Now they alternate turn, Petya moves first.

One move happens as follows. Lets say there are m ≥ 2 stickers on the wall. The player, who makes the current move, picks some integer k from 2 to m and takes k leftmost stickers (removes them from the wall). After that he makes the new sticker, puts it to the left end of the row, and writes on it the new integer, equal to the sum of all stickers he took on this move.

Game ends when there is only one sticker left on the wall. The score of the player is equal to the sum of integers written on all stickers he took during all his moves. The goal of each player is to maximize the difference between his score and the score of his opponent.

Given the integer n and the initial sequence of stickers on the wall, define the result of the game, i.e. the difference between the Petya's and Gena's score if both players play optimally.

从前，佩佳和格纳在又一次编程竞赛后聚在一起，决定玩一款游戏。由于他们认为大多数现代游戏都很无聊，因此他们总是尝试自己发明游戏。他们手头只有贴纸和记号笔，但这难不倒他们。

他们发明的游戏规则如下：最初，墙上有一排共 $n$ 张贴纸，每张贴纸上写有一个数字。现在两人轮流进行操作，佩佳先手。

一次操作的过程如下：假设当前墙上还有 $m \geq 2$ 张贴纸。当前进行操作的玩家需选择一个整数 $k$（满足 $2 \leq k \leq m$），并取走最左边的 $k$ 张贴纸（即从墙上移除它们）。随后，他制作一张新贴纸，将其放置于整排贴纸的最左端，并在上面写下该次操作所取走的所有贴纸上的数字之和。

当墙上仅剩一张贴纸时，游戏结束。每位玩家的得分等于他在自己所有操作中所取走的所有贴纸上的数字之和。每位玩家的目标都是最大化自己得分与对手得分之差。

给定整数 $n$ 和墙上初始的贴纸序列，求该游戏的结果，即：若双方均以最优策略进行游戏，则佩佳的得分与格纳的得分之差。

The first line of input contains a single integer n (2 ≤ n ≤ 200 000) — the number of stickers, initially located on the wall.

The second line contains n integers _a_1, _a_2, ..., a__n ( - 10 000 ≤ a__i ≤ 10 000) — the numbers on stickers in order from left to right.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 200\,000$）—— 墙上贴纸的初始数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10\,000 \leq a_i \leq 10\,000$）—— 从左到右依次排列的贴纸上所写的数字。

Print one integer — the difference between the Petya's score and Gena's score at the end of the game if both players play optimally.

输出一个整数——如果双方都以最优策略进行游戏，游戏结束时 Petya 的得分与 Gena 的得分之差。

In the first sample, the optimal move for Petya is to take all the stickers. As a result, his score will be equal to 14 and Gena's score will be equal to 0.

In the second sample, the optimal sequence of moves is the following. On the first move Petya will take first three sticker and will put the new sticker with value  - 8. On the second move Gena will take the remaining two stickers. The Petya's score is 1 + ( - 7) + ( - 2) =  - 8, Gena's score is ( - 8) + 3 =  - 5, i.e. the score difference will be  - 3.

在第一个样例中，Petya 的最优操作是取走所有贴纸。结果，他的得分为 $14$，而 Gena 的得分为 $0$。

在第二个样例中，最优的操作序列为：第一步，Petya 取走前三个贴纸，并放置一张新贴纸，其值为 $-8$；第二步，Gena 取走剩余的两张贴纸。Petya 的得分为 $1 + (-7) + (-2) = -8$，Gena 的得分为 $(-8) + 3 = -5$，即得分差为 $-3$。