Cho dãy số nguyên ~A = (a_1, a_2, \ldots, a_N)~ gồm ~N~ phần tử. Một dãy được gọi là dãy con của dãy ~A~ nếu nó được tạo ra bằng cách lấy một số phần tử liên tiếp trong ~A~.

Ví dụ: ~A = (1, 5, 3, -7, 2, 4)~ thì các dãy ~(5, 3)~, ~(3, -7, 2, 4)~, ~(1, 5, 3)~, ~\ldots~ được gọi là dãy con của ~A~.

Yêu cầu: Tìm dãy con của ~A~ có tổng các phần tử lớn nhất.

Input Specification

• Dòng thứ nhất chứa số nguyên dương ~N~ ~(N \le 2 \times 10^5)~.
• Dòng 2 gồm 𝑁 số nguyên ~a_1, a_2, \ldots, a_n~ ~(|a_i| \le 10^3; 1 \le i \le N)~.

Output Specification

• Chứa một số nguyên duy nhất là tổng các phần tử của dãy con cần tìm.

Sample Cases

Input #1:

9
-2 1 -3 4 -1 2 1 -5 4

Output #1:

6

Explanation #1:

• Dãy con có tổng lớn nhất là ~A' = (4, -1, 2, 1)~ với tổng bằng ~6~.