~illya~ và ~nkwn~ chơi một trò chơi với dãy số ~a~. Hai bạn sẽ lần lượt thực hiện các lượt chơi, tại mỗi lượt một bạn sẽ lấy ra khỏi dãy phần tử đầu tiên hoặc phần tử cuối cùng và cộng giá trị phần tử đó vào số điểm của mình. Trước khi bắt đầu chơi, ~illya~ được quyền sắp xếp dãy ~a~ theo thứ tự tùy ý và ~nkwn~ là người chơi trước.

Số điểm ban đầu của mỗi bạn là ~0~ và cả hai đều chơi tối ưu để điểm của mình là lớn nhất. Cho dãy ~a~, hãy tìm số điểm của ~illya~ và ~nkwn~ sau khi trò chơi kết thúc.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ - số phần tử của dãy ~a~ (~n \leq 100~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, a_3, \dots, a_n~ (~1 \leq a_i \leq 10^4~).

Output

• In ra hai số trên cùng một dòng lần lượt là số điểm của ~illya~ và ~nkwn~ sau khi trò chơi kết thúc.

Sample Input 1

3
1 2 3

Sample Output 1

3 3

Sample Input 2

4
1 2 3 4

Sample Output 2

5 5

Subtask

• ~30\%~ số test có ~n \leq 20~.
• ~50\%~ số test khác có ~n \leq 50~.
• ~20\%~ còn lại không có ràng buộc thêm.