337. Greed and Meet

0

Easy

Aniket and Bhanu, two college friends who haven't seen each other in 10 years, decide to reunite at an arcade. They plan to play a game where there are N distinct numbers arranged from left to right. Taking turns, they can choose either the leftmost or rightmost number. Both Aniket and Bhanu are greedy, so they will always choose the highest number available during their turn.
The chosen number will be added to their respective scores. Determine the final scores of Aniket and Bhanu, assuming Aniket goes first.

Input Format

The first line contains an integer N.

The second line contains N space-separated numbers from left to right.

The second line contains N space-separated numbers from left to right.

Output Format

Print two integers on a single line: Aniket's score followed by Bhanu's score, separated by a space.

Example

Input

4
4 1 2 10

Output

12 5

Constraints

1 ≤ N ≤ 1000.

Numbers are from 1 to 1000.

Numbers are from 1 to 1000.

Loading...

View Submissions

Console