~Quốc~ và ~Lan~ đang chơi một trò chơi. Luật của trò chơi rất đơn giản. Hai người chơi có ~n~ lá bài được xếp thành một hàng. Mỗi lá bài chứa một số, tất cả các số trên lá bài đều khác nhau. Các người chơi lần lượt thực hiện nước đi, ~Quốc~ đi trước . Trong lượt của mình, mỗi người chơi có thể chọn một lá bài: hoặc là lá bài ở vị trí bên trái nhất, hoặc là lá bài ở vị trí bên phải nhất. Trò chơi kết thúc khi không còn lá bài nào. Người chơi có tổng số lớn nhất trên các lá bài của mình khi kết thúc trò chơi sẽ thắng.

~Quốc~ và ~Lan~ đang tham lam. Mỗi người trong số họ sẽ chọn lá bài có số lớn hơn trong lượt đi của mình.

~Vinh~ là bạn của ~Quốc~.Anh biết ~2~ người luôn chơi tối ưu, vì vậy anh muốn xác định điểm cuối cùng, dựa vào trạng thái ban đầu của trò chơi. Hãy giúp bạn ấy

Input

Dòng đầu chứa ~1~ số nguyên ~n~ ~(1 \le n \le 10^5)~ ~-~ số lá bài trên bàn

Dòng tiếp theo in ra ~n~ nguyên dương ~a_i~ ~(1 \le a_i \le 10^9)~

Output

In ra điểm lớn nhất của ~Quốc~ và ~Lan~

Sample Input

4
4 1 2 10

Sample Output

12 5