Một dải kẻo được nối với nhau thành dây, viên kéo thứ ~i~ có vị ngon là ~a_i~, có thể xuống âm nếu nó không ngon.

Task: Bạn muốn lấy một số viên kẹo ở hai đầu này để ăn, hãy tìm tổng vị ngon của các viên kẹo lớn nhất mà bạn lấy được.

Input Specification

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(1 \le N \le 10^4)~ - độ dài của dải kẹo.
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_i~ ~(|a_i| \le 10^4)~ - độ ngon của viên kẹo.

Output Specification

• Gồm một dòng duy nhất chứa tổng vị ngon lớn nhất bạn có thể thấy được.

Sample Cases

Input #1:

10
1 -2 3 -4 5 2 -8 5 1 -3

Output #1:

8