Tèo bước vào sòng bạc với \(n\) ván bài, mỗi ván có thể thắng (\(a_i > 0\)) hoặc thua (\(a_i < 0\)). Tèo chơi liên tục một dãy các ván và muốn tổng tiền thắng là lớn nhất.

Hãy tìm tổng lớn nhất của một đoạn con liên tiếp (thuật toán Kadane).

Gợi ý: Duyệt mảng, duy trì \(cur = \max(a_i, cur + a_i)\), cập nhật \(best = \max(best, cur)\).

Input

Dòng đầu chứa \(n\) (\(1 \le n \le 10^5\)). Dòng hai chứa \(n\) số \(a_i\) (\(-10^9 \le a_i \le 10^9\)).

Output

In ra tổng lớn nhất của đoạn con liên tiếp.

Example

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

Output:

6

Giải thích: Đoạn \([4,-1,2,1]\) có tổng \(6\).