Cho một dãy các số nguyên A có N phần tử, hãy tìm đoạn con gồm các phần tử liên tiếp có tổng lớn nhất của dãy A này.

Input:

• Dòng đầu chứa số N.
• Dòng thứ 2 chứa N số, là miêu tả dãy A.

Output:

• Tổng của đoạn con có tổng lớn nhất tìm được.

Example:

Input

6
1 2 3 -1 -1 -1

Output

6

Constraint:

~0 < N \le 10^5; |A_i| \le 10^9~