Pewien profesor postanowił dać szansę niektórym uczniom na poprawę ocen z wychowania fizycznego. Ustawił na okręgu n piłeczek tenisowych i na każdej z nich napisał dowolną liczbę. Do gry zaprosił Aleksandra i Michała. Zwycięzca miał dostać szóstkę, przegrany - wiadomo co.
Rozpoczynający bierze dowolną piłeczkę. Następnie ruch wykonuje gracz drugi, i tak na przemian. Kazdy z rywalizujących, w swojej turze, zabiera jedną z piłeczek z brzegu. Gdy wszystkie piłki zostaną podzielone pomiędzy Aleksa i Michała, profesor przerywa zabawę i sumuje punkty.
Profesor postanowił pozwolić grającym ustalić, kto zaczyna. Sprytny rozkminiacz Aleks chciałby wiedzieć, czy opłaca mu się rozpocząć grę. Pomóż mu i napisz program.
W pierwszej lini wejścia znajduje się liczba n (1 <= n <= 2000). W następnym wierszu jest n liczb, każda z przedziału <1, 10000>, będących liczbami napisanymi na kolejnych piłeczkach.
Na wyjściu wypisz dwie liczby, oznaczające liczbę zdobytych punktów przez Aleksa, oraz wynik Michała, przy założeniu, że Aleks rozpoczyna grę, oraz, że Michał gra najlepiej jak się da.
Dla danych wejściowych:
5 4 5 1 2 3
Poprawną odpowiedzią jest:
9 6
[Zgłoś rozwiązanie] [Moje zgłoszenia]