ITPTIT ICPC 2021

Cô giáo Thảo cho NKT một dãy số có n phần tử vào mảng A. Cô giáo Thảo yêu cầu NKT tìm ra dãy con thuộc dãy số mà cô Thảo cho ban đầu có tổng lớn nhất.

Dãy con của dãy n là dãy có k phần tử liên tiếp (0 < k <= n).

Input

Dòng đầu chứa số nguyên n (1 < n < 10^6).

Dòng tiếp theo chứa n số nguyên của dãy  (|A_i| <= 10 ^ 6)

Output

In ra tổng của dãy con có tổng lớn nhất.

Example

Input:
7
-1 2 4 -1 6 -10 1
Output:
11