Gra w minima

Limit pamięci: 32 MB

Asia i Basia poznały niedawno grę w minima, która bardzo im się spodobała. Zasady tej gry są następujące. Na stole leży pewna liczba kart, na których napisane są dodatnie liczby całkowite. Gracze wykonują ruchy na przemian (pierwszy ruch należy do Asi). W swoim ruchu gracz wybiera dowolną liczbę kart (ale co najmniej jedną) i zabiera je ze stołu. Za taki ruch gracz otrzymuje liczbę punktów równą najmniejszej z liczb zapisanych na zabranych przez niego kartach. Gra kończy się, gdy ze stołu zostanie wzięta ostatnia karta. Każdemu graczowi zależy na tym, aby różnica między jego końcowym wynikiem a wynikiem przeciwnika była jak największa.

Asia i Basia szybko spostrzegły, że w tej grze musi istnieć strategia optymalna. Poprosiły Cię więc o napisanie programu, który dla danego zestawu kart wyznaczy, jaki będzie wynik gry, przy założeniu, że obaj gracze grają optymalnie.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę kart. W drugim wierszu znajduje się dodatnich liczb całkowitych (), pooddzielanych pojedynczymi odstępami, oznaczających liczby zapisane na kartach.

Wyjście

Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający jedną liczbę całkowitą - liczbę punktów, o które Asia wygra z Basią, pod warunkiem, że obie będą grać optymalnie (jeżeli więcej punktów uzyska Basia, to należy wypisać liczbę ujemną).

Przykład

Dla danych wejściowych:

3
1 3 1

poprawną odpowiedzią jest:

2

Wyjaśnienie do przykładu: Asia zabiera ze stołu kartę z liczbą 3, za co otrzymuje trzy punkty. Basia bierze obie pozostałe karty, za co otrzymuje jeden punkt. Gra skończy się wynikiem trzy do jednego, a zatem Asia wygra dwoma punktami.

Autor zadania: Jakub Onufry Wojtaszczyk.