Cho dãy số gồm \(n\) phần tử \(a_1,a_2,…,a_n\).

Yêu cầu: Hãy tìm một đoạn con liên tiếp có tổng lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên \(n(1≤n≤10^6 ). \)

• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa số nguyên \(a_i (|a_i |≤10^9 ).\)

Output

• Một số duy nhất là tổng lớn nhất của dãy con gồm các phần tử liên tiếp tìm được.

Ràng buộc

• Subtask 1: \(n≤200\).

• Subtask 2: \(n≤5000\).

• Subtask 3: \(n≤10^6.\)

Sample Input:

7 
8 
-10 
6 
-5 
9 
1 
-3

Sample Output:

11