Trong kỳ nghỉ hè, Hiển và Hạo đang miệt mài ôn thi vòng 2 đội tuyển HSG Tin học. Một buổi chiều, Hạo đưa ra một bài toán thú vị: Cho một dãy số nguyên $A$ gồm $n$ phần tử $A_1,A_2,\dots ,A_n$. Hãy tìm dãy con liên tiếp có tổng lớn nhất. Hiển nhanh chóng nhận ra đây là bài toán kinh điển và quyết định viết chương trình giải nhanh gọn. Hãy giúp Hiển nhé!

Dãy con liên tiếp của $A$ là một đoạn liên tục gồm các phần tử nằm liền nhau của $A$. Ví dụ, với $A=[6,-1,2,8,-4]$, dãy $[-1,2,8]$ là một dãy con liên tiếp, còn $[6,2,-4]$ thì không.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$ ($1\le n\le {10}^5$) — độ dài dãy $A$.
• Dòng thứ hai gồm $n$ số nguyên $A_i$ ($|A_i|\le {10}^9$) mô tả dãy $A$.

Kết quả

Gồm một dòng duy nhất chứa giá trị tổng lớn nhất của dãy con liên tiếp tìm được.

Ví dụ

MAX.INP

6
-1 3 -1 2 1 -5

MAX.OUT

5

Giải thích: Dãy con liên tiếp có tổng lớn nhất là $A_2+A_3+A_4+A_5=3+(-1)+2+1=5$.

Ràng buộc

• Có 50% số test ứng với $n\le {10}^3$, $|A_i|\le {10}^4$.
• Có 50% số test còn lại ứng với $n\le {10}^5$, $|A_i|\le {10}^9$.