Game with Numbers

Alice and Bob are playing a game with a list of numbers. Given an array \(a_1, a_2, \dots, a_n\), they take turns selecting a number from one of the two ends of the array. Their choices follow these rules:

• Alice can only pick an even number. On her turn, she first checks the leftmost element. If it is even, she picks it; otherwise, she checks the rightmost element.
• Bob can only pick an odd number. On his turn, he first checks the leftmost element. If it is odd, he picks it; otherwise, he checks the rightmost element.

If the current player cannot pick a valid number (i.e. neither the leftmost nor the rightmost element satisfies the condition), the turn is immediately passed to the other player without any number being selected. This process continues until all numbers have been considered.

The final score for each player is the sum of the numbers they have picked. For instance, a number \(a\) is even if \(a \bmod 2 = 0\) and odd otherwise.

Your task is to compute the final scores of Alice and Bob.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(n\) denoting the number of elements in the array.
2. The second line contains \(n\) space-separated integers representing the array.

Input is read from standard input (stdin).

outputFormat

Output two integers separated by a space: the first integer is Alice's score and the second integer is Bob's score. The result should be printed to standard output (stdout).

## sample

6
2 3 5 8 7 4

14 15