Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là tìm tổng lớn nhất của một đoạn con liên tiếp và không rỗng trong mảng.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\): số lượng phần tử của mảng.

Dòng thứ hai chứa \(n\) số nguyên:

Đây là các phần tử của mảng.

Dữ liệu ra

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

Ràng buộc

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

Ví dụ

Input

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

Output

9