Cho một dãy ~A~ gồm ~N~ số nguyên ~a_1, a_2, ..., a_N~.

Yêu cầu

Hãy tìm đoạn con ~[l, r]~ ~(1 \le l \le r \le N)~ gồm các phần tử liên tiếp ~a_l, a_{l + 1}, ..., a_{r - 1}, a_r~ của dãy ~A~ sao cho tổng ~a_l + a_{l + 1} + ... + a_{r - 1} + a_r~ là lớn nhất.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 10^5)~ là số phần tử trong dãy.
• Dòng tiếp theo chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(|a_i| \le 10^9,\ 1 \le i \le N)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là tổng lớn nhất tìm được.

Ràng buộc dữ liệu

• 20% số test của bài có ~N \le 100~.
• 20% số test của bài có ~N \le 10^4~.
• 20% số test của bài có ~N \le 10^5~ và ~a_i \ge 0~ ~(1 \le i \le N)~.
• 40% số test của bài có ~N \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

6
2 -3 8 4 -5 3

OUTPUT

12

Giải thích: ~a_3 + a_4 = 8 + 4 = 12~.