양 끝 카드 게임

두 사람이 하는 게임 Two Ends에서는 짝수 개의 카드가 한 줄로 놓이고, 각 카드에는 양의 정수가 하나씩 위를 향해 적혀 있다. 두 사람은 번갈아 가며, 자기 차례에 줄의 양 끝 중 한쪽에서 카드 하나를 가져와 자기 더미에 놓는다. 모든 카드가 없어지면, 가져간 카드의 합이 더 큰 사람이 이긴다.

한 가지 간단한 방법은 탐욕 전략으로, 항상 양 끝 중 더 큰 카드를 가져가는 것이다. 하지만 이것이 언제나 최선은 아니다. 예를 들어 줄이 3 2 10 4일 때, 탐욕 전략을 쓰는 사람은 4를 먼저 가져가지만, 첫 번째 사람은 3을 먼저 가져가는 편이 더 많은 점수를 얻는다(3 + 10 대 4 + 2).

두 번째 사람은 항상 탐욕 전략을 쓰고, 첫 번째 사람은 원하는 어떤 전략이든 쓸 수 있다고 하자. 각 게임에 대해, 첫 번째 사람의 총점이 두 번째 사람의 총점보다 많을 수 있는 최대 차이를 구하라.

입력에는 여러 게임이 들어 있다. 각 게임은 한 줄에 주어진다. 짝수 $n$ 다음에 카드에 적힌 $n$개의 양의 정수가 줄 순서대로 온다. $0$ 하나만 있는 줄은 입력의 끝을 나타내며 게임이 아니다.

$n \le 1000$이고, 한 게임에 나오는 수들의 합은 1,000,000을 넘지 않는다고 가정해도 된다.

각 게임에 대해 한 줄을 출력한다.

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

여기서 m은 게임 번호(1부터 시작)이고, p는 두 번째 사람이 탐욕 전략을 쓸 때 첫 번째 사람의 점수에서 두 번째 사람의 점수를 뺀 값의 최댓값이다.

탐욕 전략에서 두 번째 사람은 항상 더 큰 끝 카드를 가져가며, 양 끝 카드가 같으면 왼쪽 카드를 가져간다.