5.3 Pingu plays a game

Score: 100pts

Time Limit: 1.00 sec

Pingu plays a game with his friend Robby the Seal. They have \(n\) baskets. Basket \(i\) contains \(f_i\) number of fishes in it. Pingu, as we all know, loves fishes! The rules of the game are as follows - both players take turn to take each basket. In one turn, the player can take either the leftmost basket or the rightmost basket. When a player chooses a particular basket, he gets to keep the fishes the basket contains. Pingu always starts first. Once a basket is picked, it gets deleted from the row. The game ends when no baskets remain.

Pingu wants to collect the maximum amount of fishes he can. Can you help him find it? Consider both Pingu and Robby the seal to play the game optimally.

Pingu wants to collect the maximum amount of fishes he can. Can you help him find it? Consider both Pingu and Robby the seal to play the game optimally.

Constraints

\(1 \leq n \leq 1000\)

\(1 \leq f_i \leq 10^9\)

\(1 \leq f_i \leq 10^9\)

Input Format

\(n\)

\(f_1 f_2 … f_n\)

\(f_1 f_2 … f_n\)

Output Format

X

Where X is the number of fishes Pingu can collect.

Where X is the number of fishes Pingu can collect.

Example 1

Input:

6

8 15 1 1 3 7

Output:

23

Explanation:

Pingu first takes the rightmost basket and gets 7 fishes. Robby picks the rightmost basket and gets 3 fishes. Pingu again picks the rightmost basket and gets 1 fish. Robby picks up leftmost basket and gets 8 fishes. Ping picks the leftmost basket and gets 15 fishes. Robby picks the last basket.

6

8 15 1 1 3 7

Output:

23

Explanation:

Pingu first takes the rightmost basket and gets 7 fishes. Robby picks the rightmost basket and gets 3 fishes. Pingu again picks the rightmost basket and gets 1 fish. Robby picks up leftmost basket and gets 8 fishes. Ping picks the leftmost basket and gets 15 fishes. Robby picks the last basket.

Example 2

Input:

4

6 4 8 11

Output:

17

Explanation:

Pingu picks the rightmost basket first and gets 11 fishes. Then Robby the seal picks the rightmost basket and gets 8 fishes. Now Pingu selects the leftmost basket with 6 fishes and thus he has 17 fishes. Now Robby the seal picks the last basket with 4 fishes and the game ends.

4

6 4 8 11

Output:

17

Explanation:

Pingu picks the rightmost basket first and gets 11 fishes. Then Robby the seal picks the rightmost basket and gets 8 fishes. Now Pingu selects the leftmost basket with 6 fishes and thus he has 17 fishes. Now Robby the seal picks the last basket with 4 fishes and the game ends.