Two Ends

In the two-player game Two Ends, an even number of cards is laid out in a row, each showing a positive integer face up. Players alternate turns; on a turn a player removes a card from either end of the row and adds it to their own pile. When all cards are gone, the player whose cards sum to the larger total wins.

One simple approach is the greedy strategy: always take whichever end card is larger. This is not always best. For instance, with the row 3 2 10 4, the greedy player would take the 4 first, but the first player scores more by taking the 3 first (3 + 10 against 4 + 2).

Assume the second player always uses the greedy strategy while the first player may use any strategy she likes. For each game, determine the largest possible margin by which the first player's total can exceed the second player's total.

The input contains several games. Each game is on its own line: an even integer $n$ followed by the $n$ positive integers on the cards, in row order. A line consisting of a single $0$ marks the end of the input and is not a game.

You may assume $n \le 1000$ and that the sum of the numbers in any one game does not exceed 1,000,000.

For each game, print one line:

In game m, the greedy strategy might lose by as many as p points.

where m is the game number (starting at 1) and p is the maximum possible value of the first player's score minus the second player's score, given that the second player uses the greedy strategy.

For the greedy strategy, the second player always takes the larger end card; if the two end cards are equal, they take the left one.