Trò chơi vui

Ban đầu trên tường có $n$ mảnh giấy xếp thành một hàng, mảnh thứ $i$ được ghi số nguyên $a_i$. Hai người chơi lần lượt thực hiện lượt đi, người thứ nhất đi trước.

Một lượt đi diễn ra như sau. Giả sử hiện tại còn $m\ge 2$ mảnh giấy trên tường. Người đến lượt chọn một số nguyên $k$ với $2\le k\le m$, lấy đi $k$ mảnh giấy ở phía bên trái nhất (gỡ chúng khỏi tường). Sau đó người đó tạo một mảnh giấy mới, đặt vào đầu bên trái của hàng, và ghi lên đó số nguyên bằng tổng của tất cả các mảnh vừa lấy.

Trò chơi kết thúc khi chỉ còn đúng một mảnh giấy trên tường. Điểm của mỗi người bằng tổng các số được ghi trên những mảnh mà người đó đã lấy trong tất cả các lượt của mình (nói cách khác, mỗi lượt người đó được cộng thêm tổng của các mảnh vừa lấy).

Cả hai người chơi tối ưu với mục tiêu làm cho hiệu giữa điểm của mình và điểm của đối thủ là lớn nhất. Hãy xác định kết quả của trò chơi, tức là hiệu giữa điểm của người thứ nhất và điểm của người thứ hai khi cả hai chơi tối ưu.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$, số mảnh giấy ban đầu.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$, các số ghi trên các mảnh giấy theo thứ tự từ trái sang phải.

Dữ liệu ra

In ra một số nguyên: hiệu giữa điểm của người thứ nhất và điểm của người thứ hai khi cả hai chơi tối ưu.

Ràng buộc

• $2\le n\le 200000$
• $-10000\le a_i\le 10000$

Ví dụ