Optimal Candy Distribution

There are \(n\) bags of candies arranged in a line from left to right. The \(i\)-th bag contains \(a_i\) candies. Two players, Xiaolin and Xiaoyi, will distribute the bags one by one from left to right through \(n\) rounds. Initially, Xiaolin holds the distribution right. In each round, the player with the distribution right chooses to assign the leftmost bag to either himself or his opponent. The person who did not receive the bag in the current round will obtain the distribution right for the next round.

If both players play optimally to maximize the total number of candies they receive, after \(n\) rounds, determine the number of candies held by the player who collects more candies.

Game Theory Analysis:

Let \(dp(i)\) represent the optimal advantage (difference = own candies minus opponent's candies) for the player who holds the distribution right from the \(i\)-th bag onward. The recurrence can be derived as follows:

[ \begin{aligned} & dp(n+1) = 0, \[6pt] & dp(i) = \max\Bigl(, a_i - dp(i+1),, -a_i + dp(i+1)\Bigr) = \left|a_i - dp(i+1)\right| \quad \text{for } 1 \le i \le n. \end{aligned} ]

If \(S = \sum_{i=1}^{n}a_i\) is the total number of candies, then the final number of candies for the initial distributor will be \(\frac{S+dp(1)}{2}\) while his opponent will receive \(\frac{S-dp(1)}{2}\). Since we must output the number of candies held by the player who ends up with more candies, the answer is:

[ \text{Result} = \frac{S + \left|dp(1)\right|}{2}. ]

Note: All \(a_i\) are nonnegative integers.

inputFormat

The first line contains an integer \(n\) (the number of candy bags). The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the number of candies in each bag.

outputFormat

Output a single integer, which is the maximum number of candies received by the player who collects more candies.

sample

1
5

5