Luật chia bánh

Alice và Bob cùng chia nhau $N$ miếng bánh. Thứ tự phát các miếng bánh đã được ấn định trước: miếng thứ $1$, rồi miếng thứ $2$, ..., cho tới miếng thứ $N$. Mỗi miếng bánh sẽ thuộc trọn về đúng một người.

Việc phân chia diễn ra nhờ một tấm thẻ đặc biệt gọi là thẻ quyết định, ban đầu do Bob giữ. Chừng nào còn bánh chưa phát, người đang giữ thẻ quyết định sẽ:

• đưa miếng bánh tiếp theo cho một trong hai người, và
• đưa thẻ quyết định cho người còn lại.

Nói cách khác, ở mỗi lượt người giữ thẻ chọn giữa hai khả năng: nhận miếng bánh hiện tại rồi nhường thẻ cho đối phương, hoặc nhường miếng bánh cho đối phương để giữ lại thẻ. Quá trình dừng khi tất cả $N$ miếng bánh đã được phát.

Mọi miếng bánh đều ngon như nhau, nên cả hai người đều chỉ quan tâm tới việc tối đa hoá tổng kích thước phần bánh mình nhận được. Giả sử cả hai đều chơi tối ưu, hãy cho biết mỗi người nhận được bao nhiêu.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$: số miếng bánh.
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,\dots ,a_N$: kích thước các miếng bánh, theo đúng thứ tự chúng được phát.

Dữ liệu ra

In ra hai số nguyên: tổng kích thước phần bánh Alice nhận được, sau đó là tổng kích thước phần bánh Bob nhận được, khi cả hai chơi tối ưu.

Ràng buộc

• $1\le N\le 50$
• $1\le a_i\le 100000$

Ví dụ