Đoạn Liên Tiếp Tốt Nhất

Cho dãy số nguyên $A=(a_1,a_2,\dots ,a_N)$. Chọn hai chỉ số $l,r$ thỏa mãn $1\le l\le r\le N$. Điểm của lựa chọn là

Hãy tìm điểm lớn nhất có thể đạt được. Đoạn được chọn phải có ít nhất một phần tử; không được dùng đoạn rỗng.

Input

• Dòng đầu chứa số nguyên $N$.
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,\dots ,a_N$.

Output

• In một số nguyên: tổng lớn nhất của một đoạn con liên tiếp không rỗng.

Constraints

• $1\le N\le 2\cdot 10^5$.
• $-10^9\le a_i\le 10^9$.

Scoring

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

Example

7
-4 6 -2 5 -7 4 3

9