AliVu và banmkh62 đang chơi một trò chơi. Trên bàn có ~n~ tấm thẻ, mỗi tấm thẻ có một số nguyên. Hai người chơi luân phiên nhau. Trong mỗi lượt, người chơi có thể lấy tấm thẻ ngoài cùng bên trái hoặc ngoài cùng bên phải. Trò chơi kết thúc khi không còn tấm thẻ nào. Người có tổng điểm lớn hơn sẽ thắng. Vì AliVu và banmkh62 khá tham lam nên mỗi lượt chọn họ sẽ lấy tấm thẻ có số điểm lớn hơn trong hai tấm thẻ ngoài cùng. Hãy tính số điểm cuối cùng của AliVu và banmkh62.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 1000)~ — số lượng tấm thẻ.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ phân biệt ~(1 \le a_i \le 1000)~, giá trị trên mỗi tấm thẻ, được liệt kê từ trái sang phải.

Output

• In ra hai số nguyên: điểm của AliVu và điểm của banmkh62.

Ví dụ

Input

5
3 6 5 4 2

Output

10 10