English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
## Note
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 和 Gena 在另一场编程竞赛后聚在一起，决定玩一个游戏。由于他们认为现代大多数游戏都很无聊，因此他们总是尝试自己发明游戏。他们只有贴纸和记号笔，但这难不倒他们。
他们想出的游戏规则如下：最初，墙上有一排 #cf_span[n] 张贴纸，每张贴纸上写有一个数字。他们轮流进行，Petya 先手。
每一步操作如下：假设墙上还有 #cf_span[m ≥ 2] 张贴纸。当前行动的玩家选择一个整数 #cf_span[k]，满足 #cf_span[2 ≤ k ≤ m]，然后取走最左边的 #cf_span[k] 张贴纸（将它们从墙上移除）。接着，他制作一张新的贴纸，将其放在行的最左端，并在上面写下等于他本次取走的所有贴纸数字之和的新整数。
当墙上只剩一张贴纸时，游戏结束。玩家的得分等于他在所有轮次中取走的所有贴纸上的数字之和。每个玩家的目标是最大化自己的得分与对手得分的差值。
给定整数 #cf_span[n] 和墙上初始的贴纸序列，请确定游戏的结果，即当双方都采取最优策略时，Petya 的得分与 Gena 的得分之差。
输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 200 000]）——初始时墙上的贴纸数量。
第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[ - 10 000 ≤ ai ≤ 10 000]）——从左到右贴纸上的数字。
请输出一个整数——当双方都采取最优策略时，Petya 的得分与 Gena 的得分之差。
在第一个样例中，Petya 的最优操作是取走所有贴纸。结果，他的得分为 #cf_span[14]，Gena 的得分为 #cf_span[0]。
在第二个样例中，最优操作序列如下：第一轮，Petya 取走前三张贴纸，并放置一张值为 #cf_span[ - 8] 的新贴纸；第二轮，Gena 取走剩余的两张贴纸。Petya 的得分为 #cf_span[1 + ( - 7) + ( - 2) = - 8]，Gena 的得分为 #cf_span[( - 8) + 3 = - 5]，因此得分差为 #cf_span[ - 3]。
## Input
输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 200 000]）——初始时墙上的贴纸数量。
第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[ - 10 000 ≤ ai ≤ 10 000]）——从左到右贴纸上的数字。
## Output
请输出一个整数——当双方都采取最优策略时，Petya 的得分与 Gena 的得分之差。
[samples]
## Note
在第一个样例中，Petya 的最优操作是取走所有贴纸。结果，他的得分为 #cf_span[14]，Gena 的得分为 #cf_span[0]。
在第二个样例中，最优操作序列如下：第一轮，Petya 取走前三张贴纸，并放置一张值为 #cf_span[ - 8] 的新贴纸；第二轮，Gena 取走剩余的两张贴纸。Petya 的得分为 #cf_span[1 + ( - 7) + ( - 2) = - 8]，Gena 的得分为 #cf_span[( - 8) + 3 = - 5]，因此得分差为 #cf_span[ - 3]。
**Definitions**
Let $ n \in \mathbb{Z} $, $ n \geq 2 $, be the number of initial stickers.
Let $ A = (a_1, a_2, \dots, a_n) $ be the initial sequence of integers on the stickers.
Let $ S = \sum_{i=1}^n a_i $ be the total sum of all sticker values.
At each move, a player takes $ k \geq 2 $ leftmost stickers, removes them, and replaces them with a single sticker labeled with their sum. The game ends when one sticker remains.
Let $ P $ be Petya’s total score (sum of all stickers he took during his moves).
Let $ G $ be Gena’s total score (sum of all stickers he took during his moves).
**Constraints**
1. $ 2 \leq n \leq 200{,}000 $
2. $ -10{,}000 \leq a_i \leq 10{,}000 $ for all $ i \in \{1, \dots, n\} $
3. Players alternate turns, Petya moves first.
4. On a turn with $ m \geq 2 $ stickers, a player chooses $ k \in \{2, 3, \dots, m\} $, takes the leftmost $ k $ stickers, and replaces them with their sum.
5. The score of a player is the sum of the values of all stickers taken during *all* of his moves.
**Objective**
Compute $ P - G $, assuming both players play optimally to maximize the difference between their own score and their opponent’s.
API Response (JSON)
{
"problem": {
"name": "E. Funny Game",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF731E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "从前，Petya 和 Gena 在另一场编程竞赛后聚在一起，决定玩一个游戏。由于他们认为现代大多数游戏都很无聊，因此他们总是尝试自己发明游戏。他们只有贴纸和记号笔，但这难不倒他们。\n\n他们想出的游戏规则如下：最初，墙上有一排 #cf_span[n] 张贴纸，每张贴纸上写有一个数字。他们轮流进行，Petya 先手。\n\n每一步操作如下：假设墙上还有 #cf_span[m ≥ 2] 张贴纸。当前行动的玩...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $, $ n \\geq 2 $, be the number of initial stickers. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the initial sequence of integers on the stickers. \nLet $ S = \\sum_...",
"is_translate": false,
"language": "Formal"
}
]
}