Xét dãy số nguyên gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Một dãy con liên tiếp của dãy ~a_1, a_2, ..., a_n~ là dãy số nguyên có dạng ~a_i, a_{i + 1}, ..., a_j~ ~(1 \le i \le j \le n)~.

Một dãy con liên tiếp được gọi là dãy con thịnh vượng nếu tổng của các phần tử trong dãy con liên tiếp đó là lớn nhất trong tất cả các dãy con liên tiếp.

Yêu cầu

Cho trước một dãy số nguyên ~a_1, a_2, ..., a_n~. Hãy tìm tổng của một dãy con thịnh vượng của dãy đã cho.

Ví dụ: Cho dãy ~5, 3, 7, -9~. Một dãy con thịnh vượng có các phần tử là ~5, -3, 7~. Khi đó, tổng của dãy con thịnh vượng là ~S = 5 - 3 + 7 = 9~ là tổng các phần tử liên tiếp lớn nhất.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 10^6)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(|a_i| \le 10^9)~, các số trên cùng dòng viết cách nhau một dấu cách.

Dữ liệu đầu ra

Gồm một số duy nhất là tổng các phần tử của dãy con thịnh vượng của dãy đã cho.

Ràng buộc dữ liệu

• Có 50% số test tương ứng với 50% số điểm của bài có ~n \le 100~.
• Có 30% số test tương ứng với 30% số điểm của bài có ~n \le 5000~.
• Có 20% số test tương ứng với 20% số điểm của bài có ~n \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

4
8 -2 7 -17

OUTPUT

13

Ví dụ 2

INPUT

3
2 1 -9

OUTPUT

3

Ví dụ 3

INPUT

3
-5 4 -9

OUTPUT

4