Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Правило торта
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы, наверное, слышали про задачу о дележе торта. Если два человека хотят справедливо разделить кусок торта, то один человек должен разрезать кусок пополам, а другой — выбрать, кому достанется какая половина. У Алисы и Боба есть несколько кусочков пирога, и, вместо того, чтобы разрезать каждый кусочек пополам, они договорились, что каждый кусочек будет съеден одним человеком.

Они решили разделить кусочки следующим образом. Сначала они определили порядок, в котором кусочки будут распределены. У них есть специальная фишка, называемая «решающий», изначально она находится у Боба. Пока не все кусочки распределены, тот, у кого находится фишка, дает очередной кусочек пирога по своему усмотрению одному участнику дележа, а фишку — другому. Так продолжается, пока все кусочки не будут распределены.

Так как все кусочки превосходного качества, каждый участник хочет максимизировать суммарный размер кусочков пирога, которые достанутся ему. Предполагая, что оба участника принимают решения оптимально, сколько пирога получит каждый?

Входные данные

В первой строке находится одно целое число N (1 ≤ N ≤ 50) — количество кусочков пирога.

На следующей строке находятся N целых чисел — размеры кусочков (каждый размер лежит в пределах от 1 до 100000 включительно) в том порядке, в котором они будут распределены.

Выходные данные

Выведите два целых числа. Сначала выведите суммарный размер кусочков, которые достанутся Алисе, а затем суммарный размер кусочков, которые достанутся Бобу, если оба участника действуют оптимально.

Примеры
Входные данные
3
141 592 653
Выходные данные
653 733
Входные данные
5
10 21 10 21 10
Выходные данные
31 41
Примечание

В первом примере Боб должен взять кусок размера 141 себе и отдать фишку Алисе. Затем Алиса отдаст кусочек размера 592 Бобу, а фишку оставит себе, чтобы забрать себе кусочек размера 653.