Alice and Bob Card Game

Alice and Bob are playing a card game with a row of n cards. In each turn, the player whose turn it is may pick either the leftmost or the rightmost card from the row. Both players play optimally to maximize their own score. Alice always starts first.

Given the number of cards and the list of card values, your task is to determine the final scores for Alice and Bob.

The optimal play can be computed using dynamic programming. Let \(dp[i][j]\) represent the best result for the current player from the subarray of cards between indices \(i\) and \(j\) (inclusive), considering that the opponent also plays optimally. The recurrence will consider the option of taking the leftmost card or the rightmost card.

Formally, if the current player chooses the card at the left, they gain its value plus the opponent's score from the resulting subarray, and similarly for the right card.

Your program should read the input from standard input and output the final scores from standard output.

inputFormat

The input consists of two lines.

• The first line contains an integer \(n\) which is the number of cards.
• The second line contains \(n\) space-separated integers representing the values of the cards.

outputFormat

Output two integers separated by a space: the final scores for Alice and Bob respectively.

## sample

4
3 9 1 2

11 4

</p>