Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm tổng giá trị tối đa của một đoạn con khác rỗng.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước của mảng.
• Dòng thứ hai có \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các giá trị của mảng.

Output

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

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(-10^9 \leq x_i \leq 10^9\)

Example

8
-1 3 -2 5 3 -5 2 2

9