637. Sereja and Dima

0

Easy

Sereja and Dima are playing a game where they have a row of **N** cards. Each card has a unique number. The players take turns, with Sereja going first. On their turn, a player can choose either the leftmost card or the rightmost card. The game continues until there are no more cards left. The player with the highest sum of numbers on their cards at the end of the game wins.
Both Sereja and Dima are being greedy and always choose the card with the larger number on their turn.
Inna, a friend of Sereja and Dima, wants to determine the final score based on the initial state of the game. Help her.

Input Format

The first line contains an integer **N**, which represents the size of the array.

The second line contains an integer array.

The second line contains an integer array.

Output Format

Print the individual scores of Sereja and Dima.

Example

Input

7
1 2 3 4 5 6 7

Output

16 12

Constraints

1 <= N <= 1000

All elements are unique.

All elements are unique.

Loading...

View Submissions

Console