描述

在两端取牌（Two Ends）是一种两人对弈游戏。一排牌面朝上摆放着偶数张牌，每张牌上写着一个正整数。玩家轮流从队列的任一端取走一张牌并放入自己的牌堆。最终，两位玩家自己牌堆中数字之和较大者获胜。

一种简单策略是每次都取端点中更大的牌——称为贪心策略。但这并不总是最优，如下例所示：（先手如果先拿 $3$ 而不是 $4$，就能获胜。）

3 2 10 4

你需要计算，在第二个玩家使用贪心策略，而第一个玩家可以自由采用最优策略时，贪心策略最糟糕会输多少分。

输入

每个测试用例占一行。每行以一个偶数整数 $n$ 开头，表示牌的数量，后跟 $n$ 个正整数。若 $n=0$ 则结束输入，不做处理。可假设 $n\le1000$，且所有数字之和不超过 1,000,000。

输出

对每个测试用例输出一行：

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

其中 $m$ 是游戏编号（从 1 开始），$p$ 是当第二个玩家用贪心策略时，第一玩家最优可以获得的最大分差。取牌时若两端相等，应优先取左端。

4 3 2 10 4
8 1 2 3 4 5 6 7 8
8 2 2 1 5 3 8 7 3
0

In game 1, the greedy strategy might lose by as many as 7 points.
In game 2, the greedy strategy might lose by as many as 4 points.
In game 3, the greedy strategy might lose by as many as 5 points.

来源

East Central North America 2005