Sereja and Dima

Problem statement

Two players take turns removing a card from either end of a row. The first player starts, and each player always chooses the larger of the two end values. All card values are distinct. Report the total score earned by each player after every card is taken.

Input format

First line: n. Second line: n space-separated integers.

Output format

Print first_player_total second_player_total.

Constraints

1 <= n <= 1000; distinct card values are between 1 and 1000.

Sample input

5
6 2 9 1 4

Sample output

9 13