Сережа и Дима играют в игру. Правила игры очень просты. Перед игроками лежат в ряд n карточек. На каждой карточке написано число, причем все числа на карточках различны. Игроки ходят по очереди, первый ходит Сережа. На свой ход можно забрать себе одну карточку: либо самую левую карточку из ряда, либо самую правую. Игра заканчивается, когда в ряду не осталось карточек. Выигрывает тот, у кого в конце игры сумма чисел на взятых карточках больше.
Сережа и Дима действуют жадно. На своем ходе, каждый из них из двух карточек выбирает ту, на которой написано большее число.
Инна — подруга Сережи и Димы. Она знает какую стратегию используют ребята, поэтому хочет по изначальному состоянию игры определить, какой в конце игры будет счет. Помогите ей.
Выходные данные
Выведите в единственной строке два целых числа. Первое число — это количество очков у Сережи в конце игры, второе — количество очков у Димы в конце игры.
Примечание
В первом тесте Сережа возьмет карточки с числами 10 и 2, таким образом сумма Сережи 12. Дима возьмет все остальные карточки с суммой 5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 1 2 10
|
12 5
|
|
2
|
7
1 2 3 4 5 6 7
|
16 12
|