An là một nhà đầu tư chứng khoán. An theo dõi giá cổ phiếu trong \(N\) ngày, ngày thứ \(i\) có mức lãi (hoặc lỗ) là \(a_i\) (có thể âm).

An muốn chọn một khoảng thời gian liên tiếp để đầu tư sao cho tổng lãi là lớn nhất. Hãy giúp An tìm tổng lãi lớn nhất đó.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, ..., a_N\) (\(|a_i| \le 10^9\)).

Kết quả ra

• In ra tổng lãi lớn nhất tìm được.

Ví dụ

Input

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

Output

6