Đoạn Có Tổng Lớn Nhất

Cho dãy $X$ gồm $N$ số nguyên. Một đoạn con được tạo bởi các phần tử liên tiếp $X_l,X_{l+1},\dots ,X_r$, với $1\le l\le r\le N$; vì vậy đoạn luôn chứa ít nhất một phần tử.

Hãy tìm tổng lớn nhất có thể đạt được bởi một đoạn con của dãy.

Input

• Dòng đầu chứa số nguyên $N$.
• Dòng thứ hai chứa $N$ số nguyên $X_1,X_2,\dots ,X_N$.

Output

• In một số nguyên - tổng đoạn con lớn nhất.

Constraints

• $1\le N\le 2\cdot 10^5$.
• $-10^9\le X_i\le 10^9$.
• Đáp án nằm trong phạm vi số nguyên $64$ bit có dấu.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

8
-5 4 -1 2 1 -7 6 3

9