Card Game

Interview

Time limit1sMemory limit256 MB

Summary

Both players alternately take the left or right end card to maximize their own sum, and you compute the first player best total score.

Level: Medium4 of 10
Topics: Dynamic programming, Game theory
Solved: No attempts yet

Problem

Geunwoo and Myungwoo play a card game. $N$ cards lie in a row, and each card has one number written on it. Geunwoo goes first, and the two players alternate turns. On a turn, a player can take either the leftmost card or the rightmost card of the row. The turns repeat until no card is left. Each player's score is the sum of the numbers on the cards that player took.

Both players play the strategy that maximizes their own score. Given the number of cards $N$ and the number on each card, write a program that computes Geunwoo's score.

For example, suppose the cards read 4, 3, 1, 2 from the left. Geunwoo takes 4 and Myungwoo takes 3. Then Geunwoo takes 2 and Myungwoo takes the last card, 1. With both playing their best strategy, Geunwoo's score is 6.

Input

The first line has the number of test cases $T$ ( $1 \le T \le 50$ ).

For each test case, the first line has the number of cards $N$ ( $1 \le N \le 1000$ ). The second line has $N$ natural numbers separated by spaces, where the $i$ -th number is written on the $i$ -th card from the left. Every number on a card is between $1$ and $10000$ .

Output

For each test case, print Geunwoo's score when both players play their best strategy, one score per line.

Examples5

Example 1
Input
```
2
4
1 2 5 2
9
1 1 1 1 2 2 2 2 2
```
Expected output
```
6
8
```
Example 2
Input
```
1
4
4 3 1 2
```
Expected output
```
6
```
Example 3
Input
```
1
1
10000
```
Expected output
```
10000
```
Example 4
Input
```
2
2
1 10000
2
10000 1
```
Expected output
```
10000
10000
```
Example 5
Input
```
2
5
7 7 7 7 7
6
7 7 7 7 7 7
```
Expected output
```
21
21
```