Cho một dãy ~A~ gồm ~n~ phần tử ~A_1, A_2, \ldots, A_n~. Tìm dãy con liên tiếp có tổng lớn nhất của ~A~.

Dãy con liên tiếp của ~A~ là đoạn liên tục, gồm các phần tử nằm liền nhau của ~A~. Ví dụ cho dãy ~A = [6, -1, 2, 8, -4]~ thì dãy ~B = [-1, 2, 8]~ là một dãy con liên tiếp của dãy ~A~. Còn dãy ~C = [6, 2, -4]~ không là một dãy con liên tiếp của ~A~.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^5~) — độ dài dãy ~A~.

Dòng thứ hai gồm ~n~ số nguyên mô tả dãy ~A~ (~|A_i| \le 10^9~).

Output

Gồm một dòng duy nhất chứa giá trị dãy con liên tiếp có tổng lớn nhất của dãy ~A~.

Sample Input 1

6
-1 3 -1 2 1 -5

Sample Output 1

5

Notes

Dãy con liên tiếp có tổng lớn nhất là ~A_2 + A_3 + A_4 + A_5 = 3 - 1 + 2 + 1 = 5~