Trò chơi bốc sỏi theo chỉ số tăng

Trò chơi đối kháng giữa hai người chơi trên dãy đống sỏi ~1 \ldots N~. Mỗi lượt chỉ được lấy một đống và chỉ số phải tăng so với đống đối thủ vừa lấy. Người đi trước là An. Mỗi người muốn tối đa hoá tổng số sỏi của chính mình.

Yêu cầu

Cho ~N~ đống sỏi, đống thứ ~i~ có ~X_i~ viên. Hai người chơi An (đi trước) và Bình luân phiên chơi; ở lượt đầu, An có thể chọn bất kỳ đống nào; kể từ lượt sau, người đang đi chỉ được chọn một đống có chỉ số lớn hơn chỉ số đống mà đối phương vừa chọn. Cả hai đều chơi tối ưu. Hãy xác định tổng số sỏi cuối cùng của An và của Bình.

Dữ liệu

• Dòng 1: số nguyên ~N~ (~1 \le ~N~ \le 10^5~).
• Dòng 2: dãy ~X_1, X_2, \ldots, X_N~ (~1 \le ~X_i~ \le 10^9~).

Quy tắc lượt:

• Lượt đầu: An chọn bất kỳ chỉ số ~i \in \{1,\ldots,N\}~.
• Các lượt tiếp theo: nếu đối thủ vừa chọn chỉ số ~j~, người đang đi chỉ được chọn chỉ số ~k~ thoả ~k > j~.
• Mỗi lần chọn, người chơi lấy toàn bộ ~X_k~ viên sỏi của đống đó.

Kết quả

In ra hai số nguyên, cách nhau một dấu cách, lần lượt là tổng số sỏi của An và của Bình khi cả hai chơi tối ưu.

Ví dụ

Ví dụ 1

Input:
6
6 2 4 5 1 3

Output:
13 7

Ví dụ 2

Input:
1
5

Output:
5 0

Giải thích

• Ví dụ 1: Với dãy ~[6,2,4,5,1,3]~, khi cả hai đều tối ưu dưới ràng buộc chỉ được nhảy sang chỉ số lớn hơn đối phương vừa chọn, cân bằng tối ưu đạt ~13~ cho An và ~7~ cho Bình như kết quả mẫu.
• Ví dụ 2: Chỉ có một đống (~5~). An lấy đống duy nhất, Bình không còn nước đi, kết quả ~5~ và ~0~.

Chấm điểm

Toàn bộ test tuân thủ ràng buộc:

$$ 1 \le ~N~ \le 10^5,\quad 1 \le ~X_i~ \le 10^9. $$