Cho mảng ~A~ gồm ~n~ số nguyên. Tìm mảng con có tổng lớn nhất.

Input

Dòng thứ nhất gồm một số nguyên ~n~ (~1 \le n \le 10^5~).

Dòng tiếp theo gồm ~n~ số nguyên ~A_i~ (~|A_i| \le 10^9~).

Output

In ra một số nguyên là tổng lớn nhất của một mảng con.

Sample Input 1

5
9 4 5 1 10

Sample Output 1

29

Sample Input 2

5
8 3 8 -8 -7

Sample Output 2

19