Cho một dãy số gồm ~n~ phần tử. Tìm đoạn con có tổng lớn nhất của dãy ~a~.

Yêu cầu: Tìm ra tổng lớn nhất mà tìm được.

Input

• Dòng thứ nhất gồm một số nguyên dương ~n~ (~n \leq 10^6~).
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...a_n~ (~|a_i| \leq 10^9~).

Output

Một số nguyên là tổng lớn nhất của đoạn con của dãy ~a~.

Example input 1

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

Example output 1

6

Note 1

• Đoạn con có tổng lớn nhất là ~[4, -1, 2, 1]~.
• Tổng của đoạn ~[4, -1, 2, 1]~ là ~6~.