W pewnej grze, przeznaczonej dla dwóch graczy, karty ułożone są obok siebie w jednym wierszu. Talia do gry składa się z parzystej liczby kart, a na każdej karcie znajduje się dodatnia liczba punktów. Gracze naprzemiennie biorą po jednej karcie z jednego z końców wiersza. Grę wygrywa gracz, który uzbiera większą sumę punktów.
Jedną ze strategii rozgrywania gry jest strategia zachłanna zgodnie z którą gracz zawsze bierze kartę mającą większą liczbą punktów. Niestety strategia ta nie zawsze prowadzi do zwycięstwa. Weźmy dla przykładu następujące ułożenie kart:
5 4 14 7
Jeśli obydwaj gracze będą stosować strategię zachłanną, wówczas gracz 1 (rozpoczynający grę) przegra. Z tego też powodu rozpatrzymy przypadek, kiedy wyłącznie gracz 2 stosuje strategię zachłanną.
Twoim zadaniem jest wyznaczenie jaką maksymalną różnicą punktów może zwyciężyć gracz 1 w sytuacji kiedy wyłącznie gracz 2 stosuje strategię zachłanną. Jeśli na obydwu końcach wiersza znajdują się karty z identyczną liczbą punktów, wówczas gracz 2 wybiera kartę z lewego końca.
Wejście składa się z pewnej liczby zestawów danych. Każdy zestaw danych składa się z jednego wiersza zawierającego n+1 liczb całkowitych oddzielonych spacją. Pierwsza liczba w wierszu zawiera liczbę 2 ≤ n ≤ 1000 będącą liczbą kart w talii. Kolejnych n liczb całkowitych dodatnich określa liczbę punktów na każdej z kart. Liczby te występują w kolejności w jakiej ułożone są karty i są one tak dobrane, aby suma punktów na wszystkich kartach nie przekroczyła 1.000.000. Zestaw danych wejściowych zakończony jest wierszem zawierającym pojedynczą liczbę 0.
Dla każdego zestawu danych należy wypisać jaka jest maksymalna różnica punktów, którą może zwyciężyć gracz 1 jeśli wyłącznie gracz 2 będzie stosował strategię zachłanną.
4 5 4 14 7 6 7 7 7 7 7 7 6 1 2 3 4 5 6 0
8 0 3