Trọng và Bảo đang chơi 1 trò chơi. Trò chơi này sẽ có n cái hố . Mỗi cái hố sẽ có một số lượng các viên bi, mỗi hố có số lượng bi khác nhau, không hố nào giống hố nào. Luật trò này rất đơn giản. Tới lượt của ai thì người đó sẽ chọn cái hố nằm ở bên trái ngoài cùng hoặc bên phải ngoài cùng và lấy tất cả số viên bi nằm trong cái hố đó. Biết Bảo là người đi đầu tiên. Tới cuối cùng, ai có nhiều bi hơn thì người đó thắng

Đã chơi thì phải thắng nên cả 2 người đều quyết định chọn tham lam tức tối ưu nhất ở thời điểm hiện tại.

Yến là 1 người bạn của 2 người, cô ấy biết được chiến thuật của 2 người này và muốn bạn giúp cô ấy xác định kết quả cuối cùng.

Input
Dòng đầu tiên chứa 1 số nguyên n (1≤n≤1000) — số lượng cái hố. Dòng thứ hai chứa n số nguyên, được ngăn cách bởi 1 khoảng trắng, là số lượng các viên bi ở trong n cái hố đó. Mỗi cái hố đều có số lượng bi khác nhau và nằm trong khoảng từ 1 đến 1000.

Output
In 1 dòng duy nhất chứa 2 số nguyên được cách nhau bởi 1 khoảng trắng. Đó lần lượt là điểm của Bảo và Trọng lúc kết thúc trò chơi

Examples
Input

4
4 1 2 10

Output

12 5

Input

7
1 2 3 4 5 6 7

Output

16 12

Note
Ở ví dụ đầu tiên, Bảo đã chọn những cái hố có số lượng bi là 10 và 2, Vậy Bảo có 12 viên. Còn Trọng thì chọn cái hố có số lượng bi là 4 và 1, vậy tổng viên bi của Trọng là 5.