A and B Coin Game

Two players, A and B, play the following coin game. Initially, there are \( n \) coins placed in a row, where the \( i\)th coin from the left has a value \( c_i \). The players take turns removing one or more coins from the left end of the row. When a player removes coins, they must take a consecutive block starting from the left and add the total value of these coins to their own cumulative score.

The rules for how many coins can be taken are as follows:

• On the very first move, player A can take at most 2 coins.
• On each subsequent move, if the opponent removed \( k \) coins on their previous turn, then the current player can remove at most \( 2k \) coins.

The game ends when there are no coins left to take. Assuming that both players play optimally to maximize their own cumulative value, determine the maximum cumulative value that player A can obtain.

Note: This is a zero-sum game. Let the total value of all coins be \( T = \sum_{i=1}^{n} c_i \) and define a function \( f(i, M) \) which represents the maximum difference the current player can achieve (their score minus the opponent's score) starting from the \( i\)th coin with an option to take at most \( M \) coins. The recurrence is given by:

[ f(i, M) = \max_{1 \le x \le \min(M, n-i)} \Bigg(\sum_{j=i}^{i+x-1} c_j - f(i+x, 2x)\Bigg), \quad f(n, M) = 0. ]

Then, the answer for player A is computed as:

[ \text{A_value} = \frac{T + f(0, 2)}{2}. ]

inputFormat

The first line contains an integer \( n \) representing the number of coins.

The second line contains \( n \) space-separated integers \( c_1, c_2, \dots, c_n \) where \( c_i \) is the value of the \( i\)th coin.

outputFormat

Output a single integer representing the maximum cumulative value that player A can obtain when both players play optimally.

Note: It is guaranteed that the result is an integer.

sample

3
1 2 3

3