Trong một khu rừng đầy sắc màu, có hai người bạn thân là ~M~ và ~T~. ~M~ mang trong mình toàn những con số dương tươi sáng, trong khi ~T~ lại mang theo những con số âm u ám. Một ngày, ~T~ thở dài và nói với M: "Số phận tôi thật đáng buồn, chỉ toàn số âm. Tôi có ý nghĩa gì đâu?"

~M~ mỉm cười, ánh mắt tràn đầy hy vọng: "Đừng lo, ~T~! Hãy để chúng ta kết hợp dãy số của mình. Dù có những con số âm, tôi tin rằng chúng ta vẫn có thể tạo ra một điều tuyệt vời." Họ cùng nhau bày ra một dãy số dài n trước khu rừng. Khi dãy số đã hoàn thành, M bắt đầu cộng từng phần. Với mỗi bước, những con số dương tiếp sức cho nhau, và dù có những con số âm chen vào, tổng giá trị vẫn không ngừng tăng lên.

Cuối cùng, ~M~ mỉm cười với ~T~: "Nhìn xem! Dù có số âm, chúng ta vẫn tìm được tổng lớn nhất. Mỗi phần của dãy số đều có giá trị riêng."

Bạn được biết ~M~ và ~T~ đã trộn lẫn dãy số của họ với nhau tạo thành một chuỗi dài, gồm cả số dương lẫn số âm. Nhiệm vụ của bạn là tìm ra tổng lớn nhất có thể tạo ra từ chuỗi số đó, bằng cách lựa chọn những đoạn liên tiếp nào mang lại giá trị lớn nhất.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^{5})~ - đại diện cho độ dài của dãy số.
• Dòng tiếp theo gồm ~n~ số nguyên ~x~ ~(-10^{9} \le x \le 10^{9})~ - dãy số của ~M~ và ~T~ đã kết hợp.

Output

• Một số nguyên duy nhất là tổng lớn nhất có thể đạt được từ một đoạn liên tiếp của dãy số.

Sample Input

8
1 3 -2 5 3 -5 2 2

Sample Output

10

Lưu ý : Nếu trình chấm phát hiện AI sẽ bị BAN.