Optimal Card Game Strategy

In this problem, you are given a sequence of cards, each with a numerical value. Two players take turns selecting a card from either the beginning or the end of the sequence. Both players play optimally, meaning that the first player will try to maximize his score while the second player will try to minimize the first player’s score.

Formally, given an array (A[0 \dots n-1]) of card values, the first player aims to maximize his total score by choosing either the leftmost or rightmost card in each turn, and the game continues until all cards are taken. Your task is to determine the maximum score the first player can achieve if both players play optimally.

inputFormat

The first line of input contains an integer (T) representing the number of test cases. For each test case, the first line contains an integer (n) indicating the number of cards. The second line contains (n) space-separated integers representing the values of the cards.

outputFormat

For each test case, output a single line containing the maximum score the first player can achieve.## sample

5
4 1 2 9 4
3 4 4 4
4 5 3 7 10
4 8 15 3 7
6 20 30 2 2 2 10

10
8
15
22
42